Note: The quality of the end result depends largely on your eye for color. I, the author of this post, do not have a very good eye for color. Those who do would likely end up with a much more realistic final product.

Getting Gimp

A must-have for hobbyist image editors, Gimp is available for free download for all major platforms from Gimp.org. If you’re running Linux you may already have it installed, and if not, it’s probably available in your distro’s standard repositories. Ubuntu users can fetch it from the Ubuntu Software Center, or from the command prompt with:

Overview

As noted in the introduction, we cannot restore the original colors from a black & white photo, but we can add colors whose realism is only limited by your skill at color matching. We’ll do this by selecting regions of the image that should share the same color and using Gimp’s tools to apply it.
It’s important to note that there are MANY methods of applying and adjusting colors in Gimp. The method used here was chosen for speed and simplicity, and may not necessarily be the “best” way to get photo-realistic color.

Selecting a Color Region

Like color tools, Gimp provides multiple methods of selecting regions. The recommended one for this exercise is the Free Select tool.

With this tool, each time you click on the image you set a point along the general outline of the place you want to color.

Colorizing

Once you’ve selected your region, it’s time to add some color. One way is by opening Colors -> Colorize.

Apply the same process to each region you want to colorize. Don’t forget to include details like lips and the whites of the eyes if necessary. Using Presets in the Colorize window may save you some time. The colors don’t have to be exact, but get as close as you can.

Fine Tuning

If you’re as bad at color matching as I am, you likely still need to tweak the image so it doesn’t look too kaleidoscopic. Once again there are many ways to do this, but a simple way to make your colors more consistent is to adjust the color curves so that you’re essentially applying a filter to the image.
To do this, first make sure your entire image is selected and then open Colors -> Curves. Under Channel, you can select Red, Green, and Blue (optionally Alpha depending on your image). By adjusting the curves here you filter out (or emphasize) certain ranges of each color. By applying it to the whole image, we’re helping to make our manually-added colors a bit more consistent looking.

Several other color tools may come in handy, so check out some options like Brightness/Contrast, Hue/Saturation, and of course many of the great things to be found in the Filters menu.
Finally, you may need to do some manual brushing. A semi-opaque fuzzy brush would help mottle skin tone a bit, or you could create multiple color layers and move between them with layer masks.
Do you have a better way, or just want to pick on my poor coloring skills? Sound off in the comments!