How are older movies post-converted to 3D?

2D to 3D Video Conversion is the process of transforming the original 2D video to a 3D form, which in almost all cases is stereo, so it is the process of creating imagery for each eye from one 2D image. That is why the transformation is also called 2D to stereo 3D conversion, or stereo conversion.

Two approaches to stereo conversion can be loosely defined: quality semiautomatic conversion for cinema and high quality 3DTV, and low quality automatic conversion for cheap 3DTV, VOD and similar applications.

The idea is that a separate auxiliary picture known as the "depth map" is created for each frame or for a series of homogenous frames to indicate depths of objects present in the scene. The depth map is a separate grayscale image having the same dimensions as the original 2D image, with various shades of gray to indicate the depth of every part of the frame. While depth mapping can produce a fairly potent illusion of 3D objects in the video, it inherently does not support semi-transparent objects or areas, nor does it allow explicit use of occlusion, so these and other similar issues should be dealt with in a specific way.

The price on high quality stereo conversion varies in the range of $25,000..100,000 per minute according to several estimates. In your case, Titanic's 3D conversion is estimated to $18,000,000. You can read more about techniques here or read about the art of stereo conversion of some famous movies here.

3D movies are normally filmed using two slightly offset cameras.

Both images are projected onto the viewing screen, with those plastic glasses feeding one image into your left eye and the other into your right.

When a film was not shot using two offset cameras, the conversion involves manual identification of different depths in the shot, as summarized in this Gizmodo Article:

Graphic artists separate shots out into layers of depth, which can number anywhere from two layers for shots with simple blocking to eight for shots with more complex compositions. Then, the objects in each layer are carefully traced, creating a topographical map of the scene. Here, the computer steps in, simulating the second camera's perspective by generating another, slightly offset image. The images in the layers closest to the viewer are offset the most, creating the illusion of things popping off the screen, while the background is only offset slightly.

A more detailed procedure is explained at Slate.

In cases like Titanic (1997), the re-release in 3D (2012) involved almost a year of work. Using the technique of rotoscoping and 3D software, they added "depth in layers" to the whole movie. A way of understand rotoscoping is like a "digital sccisor", that allow you to separate parts of the image. And in this case, make those parts feel near or far from you as a viewer, to create the feel of depth in the image you see in the screen.