This paper explores the Intersection of two fields of research: autonomous underwater vehicles (AUVs), and archaeology in the deep sea. Archaeology in the deep sea poses a range of difficult, interesting problems for autonomous underwater vehicles. These include broad area sonar searches, target identification, and precision survey. Broad area sonar searches for archaeology have requirements similar to those in other AUV applications - collecting sonar data to locate targets for further inspection. We briefly discuss what existing vehicles can contribute to archaeological searches. We then describe the challenges for AUVs in identifying archaeological sites. Then, we discuss the importance of precision survey of archaeological sites and its implications for vehicle design and control. By "mowing the lawn" with computer-controlled tracklines over an archaeological site, an AUV could collect imagery and sonar data for precise maps of a particular site. We propose an archaeology-specific AUV to conduct such surveys and describe the requirements for such a vehicle to work in precision, instrumented environments.