The work in this thesis enables iceberg-relative navigation for autonomous underwater vehicles (AUVs) by extending seafloor mapping and terrain-relative navigation techniques to account for iceberg motion. The primary technical contributions of the thesis are two new algorithms which each account for the non-inertial motion of free-drifting icebergs: one for creating a self-consistent three-dimensional map of an iceberg's submerged surface using collected multibeam sonar data, and another which uses such a map for real-time iceberg-relative vehicle localization. The result is a two-phased approach to iceberg-relative navigation consisting of a mapping phase and a localization phase.