How can metals like magnesium and sodium burn underwater?
Your last sentence was the key.  Metals like sodium and magesium react with water according to the following equations
$$\ce{2Na + 2H2O -&gt; 2NaOH +H2 + heat}$$
$$\ce{Mg + 2H2O -&gt; Mg(OH)2 +H2 + heat}$$
Both reactions produce hydrogen gas and a lot of heat.  As the hydrogen gas bubbles out of the water it mixes with atmospheric oxygen. The intense heat ignites the hydrogen-oxygen mixture and the mixture continues to burn (possibly explosively depending upon the quantities involved) as long as hydrogen continues to be generated.