Phillip Greenspan's
Hand Coloring Photos in PhotoShop
page covers versions through 4.0, but the process changed in 5.0.

Version 5.0 of Photoshop added the "History Brush" tool.

Here are the steps in photoshop 5.0

1. Open your color image.
2. Take a snapshot of the image (small square at the bottom of the "History Palette")
3. Select "Desaturate" from the Adjust menu.
4. Change mode to Greyscale
5. Change back to RGB
6. Select the history brush from the tool palette
7. Set the history brush icon to your snapshot layer
8. Paint to your heart's content.