We present an end-to-end framework for realizing fully automated gait learning for a complex underwater legged robot. Using this framework, we demonstrate that a hexapod flipper-propelled robot can learn task-specific control policies We present an end-to-end framework for realizing fully automated gait learning for a complex underwater legged robot. Using this framework, we demonstrate that a hexapod flipper-propelled robot can learn task-specific control policies purely from experience data. Our method couples a state-of-theart policy search technique with a family of periodic low-level controls that are well suited for underwater propulsion. We demonstrate the practical efficacy of tabula rasa learning, that is, learning without the use of any prior knowledge, of policies for a six-legged swimmer to carry out a variety of acrobatic maneuvers in three dimensional space. We also demonstrate informed learning that relies on simulated experience from a realistic simulator. In numerous cases, novel emergent gait behaviors have arisen from learning, such as the use of one stationary flipper to create drag while another oscillates to create thrust. Similar effective results have been demonstrated in under-actuated configurations, where as few as two flippers are used to maneuver the robot to a desired pose, or through an acrobatic motion such as a corkscrew. The success of our learning framework is assessed both in simulation and in the field using an underwater swimming robot.