An atom of sodium transfers its electron to one of the hydrogens of the water molecule, creating a sodium ion, a hydroxide ion, and a hydrogen radical. Two of these reactions are happening alongside each other, and the two hydrogen radicals combine into a molecule of hydrogen. For other metals, I expect the electron transfer mechanism is the same, initially forming the hydroxide, but then perhaps dehydrating to the oxide.
Sodium oxide will also react with water to produce sodium hydroxide though. Unlike most other metallic oxides though, sodium oxide is ionic, meaning when it dissolves in water, there are Na+ ions and O(2-) ions. An O(2-) ion will remove a proton from a water molecule, thereby creating two hydroxide ions.