I've only read about this, and it's been at least 15 years since I saw anything in print, but I understand there are a number of algorithms used.
First, as stated, some films have been colorized by painstakingly tinting each frame by hand. (The first few minutes of Gone with the Wind were done this way, after the decision was made to film the rest in color.)
After that, several techniques are used, all based on computer image processing. The simplest approach is to break the film into individual scenes, each where the camera doesn't change, and then have a computer algorithm recognize regions of differing intensity. Someone on a computer monitor looks at the first few frames of the scene and sets the color of each region, then the computer carries that coloring through the rest of the scene, assuming that the identified regions will not morph so rapidly that the connection with their assigned colors will be lost. This technique is usually limited to colorizing the main actors and the basic background, since scenes change so rapidly in most movies,
More sophisticated techniques use image recognition algorithms to recognize (eg) a person, separate the background from the foreground, etc. Then colors can be assigned on a more global basis and some degree of shading can be accomplished as actors move from shadow to light, etc. And, since this scheme can work beyond a single scene, more effort can be put into having a human initially set the colors, so a more varied and vivid palette can be used.
I would guess (though I've never read) that technique resembling computer animation can now be used, based on techniques used for animating action movies. A sort of motion capture could be used on the original film, and then a computer animation of the action would be produced. With some careful "blending" the original film's detail could be retained while using the colors generated by the animation.