I'm in the same boat, I also just made my first Quake models. I found it helped that I had mapping experience, because in both cases, you build wireframe meshes of some sort and apply skin/textures to them.

I use QME, which can be downloaded from quakeone.com among other places; it comes with a pretty good manual which is an enlightening read.

http://www.quakeone.com/index.php?ind=downloads&op=category_view&cat_id=8

For skins I use Wally and Paint Shop Pro 4.12, which is an older shareware program (whose trial phase never expires...)

I found it helpful to set the grid size in qme to 2 or 4 units, instead of 0.1. Just read the whole qme manual.

There is also a tutorial by Preach from Quake Expo 06, which is here:

http://www.quakeexpo.com/booth.php?id=32&page=79

Also use google to look around for tutorials etc. 

I've been working on a little project to force me to learn some C++. The program takes an md3 file and a pcx skin, and outputs a mdl file. This would be a good way of skipping the bit of the tutorial which involves messing around with quark. Right now the program works, but it's pretty inflexible. For example, it combines the skins from all the components of the md3 by overlaying them onto the same skin.

It also runs on the command line, so you have to type things in each time you want to convert something. I'd like to give it a proper windows GUI interface, but that's a whole lot of extra learning I haven't got my head round yet. If anyone thinks they'd find it useful it it's current state, give a yell.