Underwater environments are emerging as a new frontier for data science thanks to an increase in deployments of underwater sensor technology. Challenges in operating computing underwater combined with a lack of high-speed communication technology covering most aquatic areas means that there is a significant delay between the collection and analysis of data. This in turn limits the scale and complexity of the applications that can operate based on these data. In this article, we develop underwater fog computing support using low-cost micro-clouds and demonstrate how they can be used to deliver cost-effective support for data-heavy underwater applications. We develop a proof-of-concept micro-cloud prototype and use it to perform extensive benchmarks that evaluate the suitability of underwater micro-clouds for diverse underwater data science scenarios. We conduct rigorous tests in both controlled and field deployments, using river and sea waters. We also address technical challenges in enabling underwater fogs, evaluating the performance of different communication interfaces and demonstrating how accelerometers can be used to detect the likelihood of communication failures and determine which communication interface to use. Our work offers a cost-effective way to increase the scale and complexity of underwater data science applications, and demonstrates how off-the-shelf devices can be adopted for this purpose.