The widespread adoption of the Wireless Sensor Networks (WSNs) in various applications in the terrestrial environment and the rapid advancement of the WSN technology have motivated the development of Underwater Acoustic Sensor Networks (UASNs). UASNs and terrestrial WSNs have several common properties while there are several challenges particular to UASNs that are mostly due to acoustic communications, and inherent mobility. These challenges call for novel architectures and protocols to ensure successful operation of the UASN. Localization is one of the fundamental tasks for UASNs which is required for data tagging, node tracking, target detection, and it can be used for improving the performance of medium access and network protocols. Recently, various UASN architectures and a large number of localization techniques have been proposed. In this paper, we present a comprehensive survey of these architectures and localization methods. To familiarize the reader with the UASNs and localization concepts, we start our paper by providing background information on localization, state-of-the-art oceanographic systems, and the challenges of underwater communications. We then present our detailed survey, followed by a discussion on the performance of the localization techniques and open research issues.