Here is how I do it...
Draw a picture on white paper, making sure the outlines are nice and thick, then scan it in.
Fiddle with the tone balance so the white paper is really white and the black is very black, leaving a fairly sharp graduation between.
Save it!
Copy the whole image into the clipboard.
Colour it in, ignoring the fact that a lot of flood-fills and area selections partially obliterate the black lines.
Once the colouring is finished, paste the original black-and-white image back over the top, and use some kind of layer effect so that thew white is ignored, and only the thick black lines are superimposed over your coloured image. (I use either "If Darker" or "Texturise", whichever works best for each image.)
While still in 24-bit colour mode, reduce the image to the correct size (practical maximum 125 wide by 200 high, but try to keep it down to 110x175 or so).
Convert the image to paletted 256-colour, making sure you use an optimised palette. The standard VGA palette is shitty! You are unlikely to need more than 32 colours, and most of mine have either 16 or 24.
Very important - TURN OFF ANTIALIASING, just for this next step.
Flood-fill the white background with a bright colour not present elsewhere in your image, with antialiasing turned off and the tolerance turned up really high (around 60-80%). You will almost certainly get the bright colour leaking into your character in at least one spot, so zoom in on the leaky area and look for holes in the black outline. When you find them, undo the flood-fill and manually draw in a few black pixels to plug the leak. Fill the background again and see if you get more leaks. Repeat the process until you are doing the flood-fill with at least 60% (but preferably 75% or higher) tolerance and no leaks.
Test the quality of the bordering by editing the palette manually. Find the background colour you are going to make transparent and change it to #FFFFFF - pure white. If that looks okay, change it to #000000 - pure black. If both of them look okay, change it again to an inoffensive colour that contrasts with the character.
Save the image as a GIF and set the background colour to be transparent.
The whole process is harder with any kind of image without black borders.
---
This signature has performed an illegal operation and has been shut down.