The ideal tool for making underwater applications viable is an Underwater Acoustic Network (UAN). Unique characteristics, such as long propagation delay of the acoustic signal and extreme volatility in the channel quality, make UANs different from terrestrial radio networks. As a result contemporary networking solutions developed for terrestrial radio networks are not applicable to UANs. In this dissertation we focus on one of the fundamental aspects of any communication network, efficient delivery of messages from their source to their destination. The first step in this regard is the development of an efficient routing protocol. Existing routing protocols designed for UANs impose some sort of restriction on the network settings making the application domain limited. Terrestrial ad hoc routing protocols are more generic but suffer from high communication overhead under water. To deal with these issues, we propose LOARP, a low overhead routing protocol suitable for UANs having arbitrary network settings. Although simulation results show that LOARP performs better than existing routing protocols, the overall performance is still poor. Further analysis shows us that the absence of a reliable MAC protocol is the cause behind this poor performance. Secondly, we study the effects of propagation delay on the reliability of MAC. Analysis shows that underwater MAC protocols have various limitations and terrestrial MAC protocols are either unreliable or inadequate. This prompted us to explore Delay Tolerant Networking which is based on the store-carry-forward paradigm. The investigation led us to remove the carry part resulting in the design of LOARP2 which employs the store-and-forward concept to aid the MAC protocol. Results show that LOARP2 significantly improves the efficiency and reliability of message delivery but at the cost of high latency. Analysis demonstrates that LOARP2 buffers messages without considering network surroundings which increases their waiting delay causing the latency to increase. To perform message buffering more intelligently, in the final step, we propose Adaptive LOARP2, which buffers messages based on channel busyness and only for as long as necessary. Simulation results show that Adaptive LOARP2 achieves the same level of efficiency and reliability as LOARP2 but with much lower and tolerable end-to-end latency.