Painting metal, does it matter if all rust is removed before?
How exactly is the water broken down into hydrogen and oxygen?

As the acid is formed and the iron dissolved, some of the water will begin to break down into its component pieces -- hydrogen and oxygen.


That's extreme oversimplification. The reaction common for active metals (not including iron) is
$$\ce{Mg + 2 H2O -&gt;  Mg(OH)2 + H2 ^ }$$
Iron does not react this way. However, it does react with acids, say, with hydrochloric acids
$$\ce{Fe + 2 HCl(aq) -&gt; FeCl2(aq) + H2 ^}$$
The reaction is quite slow even for concentrated nonoxidizing acids. However, in presence of oxygen and in diluted acids two subsequent reactions occur, the one noted above is followed by
$$\ce{4FeCl2 + 10H2O + O2 = 4Fe(OH)3 v + 8HCl }$$
The second reaction effectively removes iron from solution, significantly fastening the overall reaction.  However, even without acid present, even in slightly basic conditions iron slowly reacts with water in presence of free oxygen, forming rust. The process is hindered only at pH above 10 or at absence of free oxygen. Since natural water is usually slightly acidic due to presence of dissolved carbon dioxide, iron always rust on contact with water and atmosphere. This, actually, is a reason why concrete layer over steel frame is regulated: concrete always contains water, and surface layers quickly looses basicity due to reaction with atmospheric carbon dioxide, so steel near surface of concrete quickly rusts, increasing in volume and tearing the concrete from inside.

In the context of automobile repair work, assume a metal surface has
rust over it. Does it matter if all of the rust is removed before the
metal surface is painted? If it does matter, then why?

Yes, it does. Rust is weak, so any paint over it will hold weak. As long as the paint film over rusty part is broken, water and atmosphere contacts the metal and start to erode it, resulting in more paint film be destroyed. So it is critical to remove all rust from the surface being painted. Abrasive blasting, if you have the equipment, is probably the best way. While some paints may be applied over rust, it should be a very thin layer, and even then I would prefer traditional paint over cleaned surface anyway.