How does oil on the surface of water prevent rust?
Well, I went and searched for the solubility of oxygen in water and oil, and found this summary paper on the NIST web site: "The Solubility of Oxygen and Ozone in Liquids" by Battino, Rettich and Tominaga, J. Phys. Chem.Ref. Data., vol 12, no. 2, 1983.

Conveniently, the paper gives solubility data for oxygen in both water and olive oil.  The solubility is given both as molar fractions, and also as the Ostwald coefficient $L$, defined as the volume of gas absorbed per volume of absorbing liquid.

Given the very different molar volumes of water and olive oil, I believe the latter provides a much more useful comparison here.  Comparing tables 1 (water; note the $10^2$ factor in the header) and 25 (olive oil) in the paper, we see that the Ostwald solubility coefficient for oxygen in water is about 2,000 times higher than in olive oil:

 Temp. (K) | Temp. (°C) | L (water) | L (olive oil)
-----------+------------+-----------+---------------
    298.15 |         25 |     310.4 |        0.1269
    308.15 |         35 |     276.6 |        0.1326
    318.15 |         45 |     254.5 |        0.1383
    328.15 |         55 |     240.9 |        0.1441


So, yes, oxygen is a lot more soluble in water than in oil.  But why?

Well, if this web site is to be believed, it's because of the strong hydrogen bonding between water molecules, which causes even liquid water to maintain some degree of an ice-like lattice structure, with gaps that small gas molecules like $\ce{O2}$ can easily slip into.  Once there, the gas becomes solvated, with the strongly polar water molecules inducing a temporary dipole in the $\ce{O2}$ molecule and thus creating an attractive Debye interaction.  The overall solvation process is exothermic (i.e. releases heat), explaining why the solubility of oxygen in water decreases with temperature.