Similar to the logic used by the GIMP plugin mentioned in Roflo's answer, you can also use the color picture to colorize the gray scale picture. You then first approximately align the two pictures (using e.g. Hugin). Then take the color image, transform to XYZ colorspace and attempt to correlate the gray values in the X and Z channels to the gray values in the Y channel. This requires partitioning the image into regions of similar color, make masks for each region and just divide the X and Z channels by the Y channel to do this in a crude way. With more effort you can do a better job by splitting the image for each region up according to ranges in Y and then making different fits for X and Z.
The next step is to use the fits to colorize the black and white image. You first transform this to linear colorspace, divide it up in the same regions as the color image (you may need to tweak the alignment if it is too far off). Then you normalize the average gray value of each region to match the average Y value of the color image, and then you apply the mapping to calculate X and Z. and add these channels t the picture. Finally, you change the normalization back to what is was (X, Y and Z are then all scaled by the same factor). When you're done with all regions, you put together all the parts and then transform the image from XYZ to sRGB.