The best way (for photoshop users) as I discovered at the weekend is to load a quake skin and then go to image > mode > colour palette and then save the colour palette (either act or pal are available).
To convert to the Quake palette, I find that texmex does the best job (and has the option to remove fullbrites), and photoshop is terrible at converting to 8 bit colour.
Anyway, it's likely that there is a similar option in PSP, so grab a Quake skin from the net...
...er, or this palette file :)
http://quake.perm.ru/skin/pallette.zip (from http://quake.perm.ru/skin/skins.htm)