Recoloring is actually a fairly easy spriting process and can be simple when you get it. You don't need more than Microsoft Paint, really. The hardest thing is picking a good colour pallette for the new sprite. You just need to slowly replace one colour with another. It's simple, but kind of tedious.
A handy tip if you use Paint to replace colours is this: Make the colour you want to replace the left-click button. Make the colour you're replacing it with the right-click button. If you hold the right-click button while using the eraser tool and brush it over the colour you want to replace, it'll do it for you.
