A molecular level understanding of metal/bulk water interface structure is key for a wide range of processes including aqueous corrosion, our focus, but their buried nature makes experimental investigation difficult and means we must mainly rely on simulations. We investigate the Mg(0001)/water interface using second generation Car-Parrinello molecular dynamics (MD) to gain structural information, combined with static density functional theory calculations to probe the atomic interactions and electronic structure (e.g calculating the potential of zero charge). By performing detailed structural analyses of both metal-surface atoms and the near-surface water we find, amongst other insights: i) water adsorption causes significant surface roughening, ii) strongly adsorbed water covers only one quarter of available surface sites and iii) adsorbed water avoids clustering on the surface. Static calculations are used to gain a deeper understanding of the structuring observed in MD. For example, we use an energy decomposition analysis combined with calculated atomic charges to show adsorbate clustering is unfavorable due to Coulombic repulsion between adsorption site surface atoms. Results are discussed in the context of previous simulations of metal/water interfaces. The largest differences for the Mg(0001)/water system appear to be the high degree of surface distortion and minimal difference between the metal work function and metal/water potential of zero charge. The structural information in this paper is important for understanding aqueous Mg corrosion, as the Mg(0001)/water interface is the starting point for key reactions. Furthermore, our focus on understanding the driving forces behind this structuring leads to important insights for general metal/water interfaces.