When I was thinking about it I remembered reading two things, one was that certain gases "form" on certain electrodes. The other was something like, such and such ion "travels" towards such and such electrode. Does the molecule break up on the electrodes? Or perhaps it breaks up at a random spot between?
The water molecules form long networks of hydrogens bonds; let's imagine one such H-bonded chain that stretches from the anode to the cathode. Reduction will occur at the cathode, so the nearest water molecule (on the end of our chain) will be deprotonated and that proton will be reduced to $H\cdot$ radical, which can combine with a nearby $H\cdot$ to form the reduction product, molecular hydrogen.
Now, the water molecule that was deprotonated can re-protonate itself with the hydrogen of its neighbor (the second $H_2O$ in our hypothetical chain), likely the very hydrogen that they were sharing as an H-bond. This leaves the second water molecule deprotonated, so it fully claims the proton the third molecule was offering in their H-bond.
The process continues, with the negative charge effectively traveling the length of the chain toward the anode as each water molecule in turn briefly becomes hydroxide. This "proton hopping" behavior is known as the Grotthuss Mechanism. This animation can give you a sense of how this phenomenon happens, but note that the animation shows an acidic mechanism (extra proton, positive charge traveling) rather than the basic mechanism I described (a missing proton, with the negative charge traveling). Both are likely at play during the electrolysis of water. (Actually, the two mechanisms probably cannot be distinguished due to the simultaneous nature of the redox process, which I'm about to describe).
At the anode, hydroxide will be oxidized to $O_2$ through a few steps that aren't necessarily relevant to your question. The big idea is that the hydroxide will be created from a water molecule at the anode end of the chain of H-bonded molecules, and it will probably happen nearly simultaneously as a water molecule at the cathode end is deprotonated to form the proton reactant. Most probably both ends of our H-bonded chain of water molecules will react at more or less the same time.
If you like metaphors, think of it as a line of people each holding a basketball. Everybody passes their basketball to the right, and received a basketball from the person on their left... Except the people standing on the two ends. One will throw their basketball into the hoop, and the other will be torn to shreds and evolve molecular oxygen.