Underwater communication and networking are key enabling technologies for many current and future marine applications. Generally, the envisioned applications include environmental monitoring, aquaculture, and surveillance. On a practical level, these applications may incorporate static sensor platforms, unmanned underwater vehicles, manned and unmanned surface vehicles, and remotely controlled underwater vehicles. Long-range communication between sensors and vehicles underwater involves mapping digital information into acoustic signals that are transmitted using Piezo-electric transducers. Transmitting information acoustically is very energydemanding and is a limiting factor in several applications that comprise batterypowered systems. Further, the usable bandwidth is very narrow, typically providing data rates on the order of 0.1–1.0 kilobits/second. These are two out of several challenges to consider in network protocol design. This thesis’s main focus has been enhancing the applicability of flooding-based routing protocols by dynamically controlling the modems’ transmission powers and adaptively selecting the fastest possible communication method. Simulations and field experiments have shown that a distributed k-Nearest Neighbor Power Controller can achieve significant energy savings. Further experiments of a distributed link adaptation method with minimal overhead have achieved improved channel utilization and throughput in a time-varying environment. Lastly, as heterogeneous systems of vehicles and sensor platforms generally incorporate diverse communication hardware with different capabilities, they must negotiate what method and parameters to use before any actual data can be transferred. Herein, a promising method that could be used for this negotiation process in a ”first-contact” protocol was also evaluated through field experiments.