As the technology behind autonomous underwater vehicles (AUV) becomes more feasible, it is possible to use fleets of AUVs for coordinated missions such as area mapping, surveillance, etc. The AUVs are typically sent by a central node such as a submarine and move autonomously. Although there is no need for continuous monitoring of AUV nodes, the central node may occasionally need to send a broadcast message to all nodes in the fleet to announce a change in mission; e.g. ordering nodes to return back to the base. To address this need, reliable and low-latency broadcast algorithms for underwater networks are needed. Here we investigate the performance of probabilistic broadcast for AUV networks where the AUVs are not aware of locations of their neighbors. Our results indicate that probabilistic broadcast significantly improves average and maximum delay along with energy consumption in comparison to simple flooding especially for dense networks.