This is probably really obvious, but I really don't understand. Why does oxygen dissolve in water when oxygen is a nonpolar molecule and water is a polar molecule? It's obvious that oxygen does dissolve, or else fish could not survive, but I'm confused on how it does so.
Oxygen is relatively insoluble in water, its solubility being only 264 $\mu M$ at $25^oC$. That explains in part why you (and fish) require dedicated oxygen carriers in your blood to transfer sufficient oxygen around your body.
That oxygen is weakly soluble can be explained, as you point out, on the basis of the hydrophobic effect, which amounts to saying that water likes to hydrogen bond, and an oxygen molecule is not very good at that compared to another water molecule.
That oxygen is soluble at all can be explained on two grounds. First, statistics, just the random mixing of matter. Some oxygen molecules will happen to find their way into water and not find their way out for a while. The other explanation is that oxygen is not entirely nonpolar: it lacks a permanent dipole moment, but it is polarizable. Even molecules that we think of as highly water repellent can exist as liquids (oxygen is a gas at room temperature but can be cooled into a liquid state), which means something must be keeping them together, and that is dispersion forces due to the polarizability of all atoms and molecules.