Oxygen reduction - beginner level I am embarrassed to ask but I don't get something really basic.

When molecular oxygen and hydrogen react to produce water, we say the oxygen has been reduced and the hydrogen has been oxidised. Reduction, I understand, is the gain of electrons.

So I look at the oxygen atoms prior to the reaction and it seems to me each has six of its own plus two more that are shared.

And I look at the oxygen in the water molecule and it has... six of its own and two that are shared.

So in what sense has it gained electrons?

Of course, before posting this question I have searched and read for several hours. All I can find is talk of half-reactions. The clue here seems to be that the oxygen is ionised to $\ce{O_2-}$ prior to reacting with $\ce{2H+}$. But this just confuses me. Maybe this intermediate step does involve reduced oxygen but the end point is still the same number of electrons as we started with, so if it does get reduced it must be oxidised again immediately afterwards, for no net effect.

Where am I going wrong?
This is a really good question which I've never given much thought about.
I'll try to explain the reason as much as I know it. There may be a better explanation.

The reaction can be represented as - 
$$\ce{2H_2 + O_2 &lt;=&gt; 2H_2O}$$ 

Now in O2 you have a structure like 
$$\ce{O\dbond O}$$

And in H2O you have a structure like (ignoring the tetrahedral hybridisation and bent shape)

$$\ce{H\sbond O\sbond H}$$

We know that Oxygen is second most electronegative element after fluorine, which is because of it's small size and strong effective nuclear pull towards electrons.

Hydrogen on the other hand, is not as electronegative as Oxygen even after having a small size, because of very less effective nuclear pull.

When a bond between H and O is formed, O pulls the shared pair of electrons towards itself because it is more electronegative than H. This is the "gain" of electrons. The atoms do not actually take up electrons (when it is covalent bond) but pull it towards themselves, thus getting reduced. You will not find this "gain" or pull of electrons in the O-O bond because they have equal pulls, hence 0 oxidation state. But in water, Oxygen has +1 oxidation state.

Similarly, for hydrogen, it pushes the electrons towards Oxygen in water. Not exactly losing the electrons but density of electrons around Hydrogen atom decrease due to this push by hydrogen and pull by Oxygen. Thus it has "lost" it's electron, becoming positively charged which wasn't the case when it was in H2
Also, you'll notice that when more bonds are formed, there is more change in oxidation state of the atom.

Hope this helped.