It comes from a combination of Henry's law and Le Châtelier's principle. Henry's law is
$$p=k_hc$$
where $p$ is the partial pressure of the gas, $k_h$ is the Henry's law constant and $c$ is the concentration of the gas (because liquids and solids are not affected as much as gases, if at all). This means that with a greater pressure comes a greater concentration, and with a lower pressure comes a lesser concentration, and vice versa
Le Châtelier's principle states that if the pressure, concentration, temperature or volume of a system changes, something else will change to compensate and swing the whole thing back into equilibrium. If there is a greater pressure, there will therefore be a grater concentration. A greater concentration means there is a greater solubility.
The UC Davis Chem Wiki (I didn't see that DrMoishe Pippik had linked to it until after I posted this!) is rather helpful - much more helpful than Wikipedia, in this case.