Programs for making Skins and/or Textures:

Paint Shop Pro: This is one of the best programs for making skins and textures. Mostly all of the top artists use the program for one reason or another. I have centered most of my tutor on this program because the shareware is free for download.

Adobe Photoshop This is another program that most artists use. You can download a demo from the linked site, but you can't save files in the demo so it is useless.
Grab this plug-in for photoshop that lets you open and save .WAL files used for q2 textures (this plug-in also works for Corel Photopaint

NPherno's Skin Tool A freeware program that allows you to draw directly on MD2 models in 256 palettes. This program is very nice for learning how skins wrap around models

MS Image Composer Though this is a nice program, not many people use it. I have it, but I do not use it very much. It has some nice features, and if you have it, you should check it out.

AdQuedit This is a great program for extracting files from the Quake/Quake2/HeXen2/etc. PAK files. It also allows you to place skins on MDL models, create PAK files, create and edit WAD files, and many more things. I use this program a lot.

 

Programs for making Models:

qME This is about the easiest program to start with if you want to learn models. I have made quite a few models with this, and it's good. You will need to get the full version so that you can make your models have a larger amount of frames. You can also make skins with this program.

3d Studio MAX: This is a powerful, expensive program for making models. I can not answer any questions on how to use it, because I have not yet had the time to learn it very well.

Lightwave: Very popular, expensive modeling program used by many top modelers, software companies, etc.

Quake 2 Model Editor This is a free program (if I'm not mistaken) that I use a lot now. What I use it for is it's great model converting abilities. All my models that are in MD2 format were converted with this program.
Go to the Tools section of this page, and you can download it.

Meddle I really don't use this much, but it's a classic. ;)