Autonomous Underwater Vehicles (AUVs) are powerful tools for exploring, investigating and managing our ocean resources. As the capabilities of these platforms continue to expand and they continue to mature as operational assets, navigation remains a fundamental technological component. This chapter presents a road map for the vehicle designer to aid in integrating the latest navigation methods into new platforms for science, industry and military platforms. Along the way, we point to emerging needs where new research can lead directly to an expansion of the operational abilities of these powerful tools. To accomplish this we start by describing the problem, explaining the needs of vehicle users and the challenges of autonomous localization. Next we explain the state of practice, how operational assets currently solve this difficult problem. To expand this explanation we present new research targeted at helping AUV builders to make the complex tradeoffs in creating a platform with the appropriate navigation solution. We conclude with an overview of the latest research and how these advances might soon become available for AUV operations in new environments such as the littoral zone, at the poles and under-ice. Throughout this chapter we attempt to reach across the disciplinary boundaries that separate the researcher from the operator.