This paper reports on a factor graph simultaneous localization and mapping framework for autonomous underwater vehicle localization based on terrain-aided navigation. The method requires no prior bathymetric map and only assumes that the autonomous underwater vehicle has the ability to sparsely sense the local water column depth, such as with a bottom-looking Doppler velocity log. Since deadreckoned navigation is accurate in short time windows, the vehicle accumulates several water column depth point clouds— or submaps—during the course of its survey. We propose an xy-alignment procedure between these submaps in order to enforce consistent bathymetric structure over time, and therefore attempt to bound long-term navigation drift. We evaluate the submap alignment method in simulation and present performance results from multiple autonomous underwater vehicle field trials.