Underwater marine object detection, as one of the most fundamental techniques in the community of marine science and engineering, has been shown to exhibit tremendous potential for exploring the oceans in recent years. It has been widely applied in practical applications, such as monitoring of underwater ecosystems, exploration of natural resources, management of commercial fisheries, etc. However, due to complexity of the underwater environment, characteristics of marine objects, and limitations imposed by exploration equipment, detection performance in terms of speed, accuracy, and robustness could be degraded dramatically when conventional approaches are used. Deep learning has been found to have significant impact on a variety of applications, including marine engineering. In this context, we offer a review of deep-learning-based underwater marine object detection techniques. Underwater object detection can be performed by different sensors, such as acoustic sonar, or optical camera. In this paper, we prefer to focus on vision-based object detection due to some significant competitive advantages. To facilitate a thorough understanding of this subject, we organize research challenges of vision-based underwater object detection into Four categories, namely image quality degradation, small object detection, poor generalization, and real-time detection. We review recent advances in underwater marine object detection and highlight advantages and disadvantages of existing solutions for each challenge. In addition, we examine the most extensively used datasets in detail and critically. Comparative studies with previous reviews, notably approaches that leverage artificial intelligence, and future trends on this hot topic are also presented. * This work has been published on Sensors.