I promised a simple tutorial a few days ago. Well, here's a start.
I use Gimp, a freeware image editing program, whenever I have to change colors of sprites. Also, in this tutorial I use a sprite already extracted from the game.
I'm starting with a seraph, the Caelum mage, and I'm trying to change it into a red-robed mage suitable for the Fiery Caelum mod. To start with, I open the extracted sprite in Gimp. The image has to be saved in a lossless format, like .bmp or .tga. Targa is better because it's much smaller, but I use MsPaint when extracting sprites so I often start from a .bmp. Gimp has multiple windows floating all around the screen, but usually I only use four: the GIMP main toolbox (tool/color selection), tool options window, the image window, and the layer window. The undo history window is also useful, because it allows you to quickly undo/redo multiple changes if you realize you've made a mistake some time ago. You can close these floating windows as you can close any other window, but closing the toolbox will close whole GIMP. To set a window visible, choose 'Windows' from the toolbar of the image window (after you've opened the image you want to edit).
About the basic tools you'll want to use:
The five tools in top-left, those marked with brown dots, are selection tools. Square and triangle select large areas and lasso selects uneven areas, wand selects areas of similar color and the fifth one selects all color close enough to a given value. The four first can be used to add to a current selection, or to remove from it, by holding Ctrl or Shift pressed. When you move a selector tool to the image area, you'll see a small + or - sign to indicate whether it adds to or removes from the current selection. To fully use the color chooser tool, change the border value in the tool options window. This window changes according to the tool you've chosen, and controls transparency of pencil and fill tools.
The cross formed by four arrows is a tool for moving selections. It's usually automatically chosen when you just hold and drag the selection.
In the middle row, I've marked the fill tool with a blue dot. You use this tool to change the color of the shadow and the background. Its Tool Options window is very important, because you have to choose between filling areas of the same color or the whole selection, and the transparency of the color. If you will the background with 50% black, you will get a grey instead of the pure black background, etc, and it can be confusing before you realize what's happening.
A little right from the fill tool is the pen tool, marked by a blue X. I've also marked the brush tool with a blue X. You have to change the brush to a 1x1 dot if you want to do pixel editing.
The color chooser is the one with a black rectangle partly over a white rectangle. You'll use that one a lot.
I also marked the zoom, in the bottom of the Image window, in orange. You want to see the sprite clearly when you edit it.