Communication underwater is challenging because of the inherent characteristics of the media. First, common radio frequency (RF) signals utilized in wireless communications cannot be used under water. RF signals are attenuated in such as way that RF communication underwater is restricted to very few meters. As a result, acoustic-based communication is utilized for underwater communications; however, acoustic communication has its own limitations. For example, the speed of sound is five orders of magnitude lower than the speed of light, meaning that communications under water experience long propagation delays, even in short distances. Long propagation delays impose strong challenges in the design of Data Link Layer (DLL) protocols. The underwater communication channel is noisy, too. The bit error rate (BER) can also change depending on depth and other factors, and the errors are correlated, like in wireless communications. As in wireless communications, transducers for acoustic communication are half duplex, limiting the application of well-known detection mechanisms in Medium Access Control (MAC) layer protocols. Further, known problems like the hidden and exposed terminal problem also occur here. All these aspects together make the underwater communication channel to have the worst characteristics of all other known channels. Because of these reasons, underwater scenarios are complicated to implement, especially when they have underwater autonomous vehicles exchanging information among them. This dissertation proposes data link layer protocols in support of swarming of underwater autonomous vehicles that deal with the problems mentioned before. At the MAC sublayer, a MAC protocol called 2MAC is introduced. 2MAC improves the throughput of the network using the multichannel capabilities of OFDM at the physical layer. At the logical link control sublayer, a protocol named SW-MER is proposed. SW-MER improves the throughput and the reliability combining the well-known stop and wait protocol with the sliding window strategy, and using an exponential retransmission strategy to deal with errors. 2MAC and SW-MER are evaluated and compared with other protocols using analytical means and simulations. The results show that by using 2MAC, packet collisions are considerably reduced and the throughput improved. In addition, the use of SW-MER improves the packet delivery ratio over existing mechanisms. In general, the evaluations indicate that the proposed data link layer protocols offer a better communication alternative for underwater autonomous vehicles (UAV) than traditional protocols.