How did they color old black and white movies?
There is no way of recovering the original color information from a black and white photo, so whether Einstein (resp. Waheeda Rehman) was wearing a pink or green sweater (resp. Dupatta) is up to your imagination.

Historically, this has been done by hand, by painting over the film. The first digital techniques to automate the process consisted in "painting" a few dots of color on each frame, at the center of each uniformly colored region, and using something like a voronoi partition + some blurring to get a color map for each frame (see for example US patent 4606625).

Today, this can be done relatively easily (though manually) with video editing software, by using vector masks to indicate regions of uniform color on a few keyframes, and interpolating between them. Then a color transform is applied to each mask. See it in action here.

Standard image segmentation and region tracking techniques can be used to automate the task of segmentation and the marking of regions on each keyframe - for example by propagating manual annotations to similar/adjacent pixels in space/time, or by detecting uniformly textured regions. Texture and gray level similarity can be used to propagate color cues from a color image to a greyscale image depicting a similar subject - in this case the manual process only consists in finding a template color image - this later task can be itself automated using content-based image retrieval techniques.