Sounds good, I'm all for helping, but oh how I loathe to hold hands.
Yes you will need Photoshop. In theory the plugin also works with Paintshop Pro, though I could never get it working as well.
If you're looking to get serious into art, I'd really suggest Photoshop CE, or later. There is a tool found in CE that isn't in the previous versions. (I'm currently using 7.0, and really miss my CE client). It was basically a "smart shader" brush. Where you pick a base color to change to, then it intelligently overlays it using the existing color gradients of what you're painting over. You can do the same thing via selecting an area, and just changing hue/saturation values. This brush however allowed for much softer blends, and streaks.
If you wanna see the difference in shading, compair my blood work on the following:
Photoshop CE brush
Photoshop 7 Hue/Shading
Also I think someone modded it somewhere else to work with the older Macromedia Fireworks MX edt. Though I could be off my rocker on that last one.