I'm adding another answer, representative of another mechanism, which I think is probably more likely than the one I proposed. It follows a similar line to the previous mechanism, but involves the adsorption of water molecules onto the cathode and anode. I will consider the reactions at the anode and the cathode separately, like in my previous mechanism.
Water is a polar molecule - the oxygen atom is more electronegative (the AOs on oxygen are lower in energy than the 1s orbital on the hydrogens, which contribute to the bonding MOs) than the hydrogen atoms, and thus the molecular orbitals will have a higher electron density on the oxygen than on the hydrogen. This gives the oxygen a small negative charge, and each hydrogen a small positive charge - not a full, ionic charge.
Because of this charge liquid water has a network of hydrogen bonding, as the positively charged hydrogen attracts a lone pair from another oxygen, thus producing a hydrogen bond - an attraction between the water molecules.
At the cathode (-ve electrode) the water molecules align themselves with this negative charge on the metal cathode. The hydronium ions are reduced by the negative metal electrode. Thus we have $$\ce{H3O+--M + e- -> H2O + H-M}$$
This explains the production of hydroxide ions - turning the solution basic at the cathode. The hydrogen is bound to the metal , using a d-orbital. (If you're interested look up hydrogen adsorption onto metal surfaces). These hydrogen atoms are able to diffuse across the metal surface, in two dimensions, kind of like skating across an ice rink - you can't jump, but you can skate easily across it (unless you're really good!). These hydrogen atoms can then react together, forming hydrogen gas. Consider the equilibrium of water:
$$\ce{H2O + H2O <=> H3O+ + OH-}$$
Decreasing the concentration of $\ce{H3O+}$ means there is proportionally more $\ce{OH-}$ than $\ce{H3O+}$, which results in the solution near the cathode becoming basic. The hydrogen bound to the metal is not particularly stable - therefore a pair of hydrogen atoms can react, becoming $\ce{H2}$, as the hydrogens are able to diffuse across the surface of the metal.
At the anode (+ve), we know that $\ce{O2}$ is produced. Again the water molecules align themselves to the charge - the negative oxygen is attracted to the positive metallic anode. The positive metal will interact with the electrons involved in bonding in water. We can envisage this as the positive metal "pulling" electron density from the oxygen. This in turn pulls electron density from the two bonds, joining the oxygen and the two hydrogen atoms. This is the inductive effect - where a positive charge is transmitted through atoms - the electron withdrawing effect. This weakens the $\ce{H-O}$ bonds. The hydrogen atoms are then solvated, to form the hydronium ion, $\ce{H3O+}$. Reaction:
$$\ce{2H2O + H2O -> 2H3O+ + O + 4e-}$$
The 4 electrons are then used to reduce the hydronium ion at the cathode - remember this is a circuit. The oxygen remains bound to the metal, and then reacts with another oxygen to form $\ce{O2}$.
I think this mechanism is more likely than the other I proposed. I am not sure about how the oxygen is bonded to the metal - in a normal coordination complex the metal donates electrons, forming a coordinate/dative bond, instead of oxygen donating a lone pair to form a dative bond. However, in this case the metal is positively charged, with an active potential difference - energy is being put into the system. I would be interested for more experienced/knowledgable people to improve this mechanism and point out reading on this.