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.