cliverlong, as an electrochemist (PhD student at the moment) I can say that the oxygen evolution reaction and the oxygen reduction reaction are still heavily debated for mechanism. In my research it seems reasonable to say that oxygen reduction goes through the intermediate of hydrogen peroxide.
In oxygen evolution what will happen is that the surface of the electrode (platinum in many cases) will first form surface hydroxides: Pt-OH, which at higher potentials will form surface oxides Pt-O. Now
In neutral/acidic media:
Pt* + H2O --> Pt-OH + H+ + e- (the Pt* stands for empty Pt surface atom)
Pt-OH --> Pt-O + H+ + e-
and the last step may be Pt-O + Pt-O --> 2 Pt* + O2, or it may be a simultaneous: Pt-O + Pt-OH --> Pt* + Pt-O2 + H+ + e-, with the oxygen then leaving the surface.
key is: water will first adsorb on the surface, form surface hydroxides and oxides, and then react to oxygen
In alkaline media there is a surplus of OH-, which will adsorb on the electrode at lower potentials. so:
Pt* + OH- --> Pt-OH + e-
and then again
Pt-OH --> Pt-O + H+ + e-
and Pt-O + Pt-O --> 2 Pt* + O2, or Pt-O + Pt-OH --> Pt* + Pt-O2 + H+ + e- with Pt-O2 --> Pt* + O2
I used Pt as electrode material in this case, as it is the most common. Other metals (or carbon) are possible, but may corrode because of the high potential of the oxygen evolution reaction.