One the key cost and complexity drivers for autonomous underwater vehicles (AUVs) is navigation. Since GPS signals cannot penetrate water, AUVs traditionally rely on inertial or acoustic navigation to know their location underwater. Although accurate inertial navigation systems (INS) or Doppler velocity logs (DVL) help reduce the error of dead reckoning underwater, they are key cost drivers. Deploying acoustic beacons increases operational complexity and cost. We have developed techniques for cooperative navigation of a team of AUVs using a single vehicle with accurate navigation (either equipped with INS/DVL, or an autonomous surface vehicle with access to GPS). We have also developed techniques to cooperatively navigate a team of AUVs using distributed terrain sensing, with none of the vehicles having INS/DVL/GPS. These techniques enable teams of AUVs to be used for underwater tasks at much lower cost and complexity than previously possible.