With the development of various mobile ad hoc networks, and in order to monitor and explore the underwater environments conveniently, underwater wireless sensor networks (UWSNs) have emerged and attracted the increasing attentions of researchers. UWSNs can be widely utilized in many underwater scenarios such as marine environment monitoring, resource exploitation, underwater biological research, shipwreck search, underwater rescue, and so on. A UWSN is significantly different from the traditional wireless sensor networks, due to the irregularity of underwater acoustic communications and the complexity of underwater environments. Moreover, a UWSN is usually composed of two types of nodes: Anchored nodes and mobile nodes. All these bring some new challenges to the technique of message dissemination in UWSNs, such as the complex movements of nodes and the uncertain future links. Therefore, a reasonable message dissemination algorithm for UWSNs will be helpful to improve the data transmission efficiency. According to the characteristics of UWSN topologies, this study applies a link prediction method for the message dissemination, and an index of spatial-temporal common neighbors is specially introduced to analyze the potential links between nodes. In addition, compared with the mobile nodes, each anchored node typically has a larger communication range and a stronger computing power, and thus each anchored node can play the role of an edge computing server to further improve the link prediction results. Finally, the next-hop relay nodes can be selected according to the obtained link prediction results. Simulation results show that the proposed algorithm can improve the delivery ratio and reduce the propagation delay of data messages while the number of forwarded message copies is confined.