I have made a few of these types of textures using the "lighting effects" filter built in to Photoshop. From Phineus's description above, it sounds like Paintshop has a similar filter. I recently bought Photoshop Elements for my wife (I am really impressed with PE for the price), it also has the "lighting effects" filter.
You can see a bit of the filter in action at this site
http://www.webreference.com/graphics/column15/
Check out the Texture Channel page, this is a really neat effect, a form of bump mapping.
Making this effect look good in the game is the hard part. Phineus did a fantastic job on Alphaville, so take his advice and don't expect to show this kind of effect on only one texture square, I don't think you have enough pixels to work with. I think Dark Star had a more defined line between the light and dark areas, which seemed appropriate for the setting, and could have been done with the technique Winterkill described.