Even in "de-ionized" water, some fraction of the water molecules in the bulk will dissociate into $\rm H^+$ and $\rm OH^-$ ions.
In electrolysis, the $\rm H^+$ ions migrate towards the cathode, where they find each other, steal electrons from their surroundings (including the cathode) and form $\rm H_2$ gas. Likewise the $\rm OH^-$ ions migrate to the anode, further dissociate, and form $\rm O_2$ gas. But these migrations are mostly of ions that are already near the electrical terminals. The bulk migration of ions in the fluid, like the "drift velocity" of electrons in a metallic circuit, is surprisingly slow.