Ok, a good paint program is Paint Shop Pro 7, you can download the trial at the jasc website:
www.jasc.com I believe.
(Sorry about the next part, we haven't got the game here in Aus, so I'm going by the demos) In the main directory or something, there should be a bunch of .pk3 files named pak#. They contain the files, such as models, skins, hud files whatever. Open them with a pak editor or whatever, if you have QERadiant, you can d/l pk3man plugin, which allows easy browsing of .pk3 files. You can also use winzip or something to open them up. Once you find the right directory, unzip the texture files (which should be .tga files, as long as they didn't change it) and you can edit them in PSP. You can find millions of tutorials on how to use PSP, just use a search engine or whatever, or someone nice enough on these message boards might give you a really helpful link.