So partial pressure of a gas dissolved in a liquid can be thought of as the pressure exerted by the dissolved gas molecules that bounce around in the solvent.
The solubility of a gas can be thought of as how energetically favorable it is for the gas molecules to stay in solution. Chemically speaking, the more non-covalent bonds that gas molecules can form (H bonds, van der waals, etc.) with the surrounding solvent molecules, the more favorable it is to stay in solution and thus the higher the solubility.
So a good visualization of the process is the higher the solubility, the more bonds tie the gas molecules down, and the less they like to bounce around and exert pressure. Thus, for the same number of molecules, those of a low solubility gas will bounce around more (because they have fewer bonds tying them down) and lead to higher partial pressure than those of a high solubility gas. Based on this, if you add molecules at the same rate for both gases, the one with a lower solubility would see a faster rise in partial pressure.
As for O2 and PaO2. When you are comparing different concentrations of the same gas, then solubility (and concentration) of that gas is directly proportional to partial pressure. That's because the more molecules, the more likelihood of collisions with the solution surface, and thus higher pressure exerted.
tl;dr:
1. Different concentrations of the same gas: partial pressure is proportional to concentration
2. Same concentration of different gases: partial pressure is inversely proportional to solubility
