The propagation of visible light underwater suffers rapid attenuation and extreme scattering. This, in combination with the limited camera-to-light separation available on most imaging platforms, places severe limitations on our ability to optically image large areas of the sea floor at high resolution. We present a general framework for mosaicking large areas underwater with a specific emphasis on the issues that are unique to the underwater environment. At the individual image level, we examine the role of attenuation, scattering, and camera to light separation and present the tradeoffs involved in optimizing a particular imaging geometry. We also examine the arbitrary image-registration problem in the face of conditions prevalent underwater, namely a moving nonuniform lighting source and the effects of a featureless unstructured terrain. Our analysis is based on photomosaics encompassing several hundred images on archaeological, forensic, and geological expeditions from a diverse set of imaging platforms, including the NR-1 nuclear submarine, the manned submersible Alvin, the Argo towed vehicle, the Jason remotely operated vehicle, and the ABE autonomous underwater vehicle.