The first thing you need to do is install the WAL plugin.  Grab that here.  Extract the wal.8bi file to Paintshop Pro's plugin formats directory (most likely "C:\Program Files\Paint Shop Pro 5\Plugins\Formats\"):

Once you've done that, fire up PSP and create a new image.  The image must have dimensions in multiples of 8 (64x64, 128x128, etc.):

Now you're ready to make your texture.  I'll just make a simple "blah" texture for demonstration purposes:

Once you're done, you'll need to load the Quake2 palette.  If you're making textures for a mod such as Paintball II that has a custom palette, you'll need to load that instead.  You can grab the JASC palette files for Quake, Quake2, and Paintball2 here.  To load a palette go to Colors|Load Palette... or hit Shift+O:

Hopefully you won't get too much color loss.  If the image looks really crappy after you load the palette, you might want to redo it so it uses colors closer to those of the ones in the palette.

If it looks good, you're ready to save it.  Hit F12 or go to File|Save As...  For the "Save as type" select WAL.  Change your directory to quake2\<moddir>\textures\<texturedir>\.  I'll just save my "blah" in quake2\baseq2\textures\jitspoe\:

It will prompt you for the full texture name.  You can put in the <texturedir>\<texturename>, but it works fine if you just use the texture name again (without the .wal):

If you want to have an animated texture, enter the name of the next texture in the animation under "Enter Animation Texture Name."  When you get to the last texture in the animation, enter in the name of the first texture so it loops.

Note: This tutorial was written for JASC Paint Shop Pro 5.0.  There may be some slight differences in other versions.
If you want the same tutorial for Photoshop, click here.

If I left out any details, screwed something up, etc, email me: jitspoe