Buteyko breathing [1] and high-intensity interval training [2]. YMMV, etc.

[1] http://store.breathingcenter.com/books---in-english/buteyko-breathing-manual-download

[2] e.g. "sprinting" on an elliptical

Sleep apnea is caused by low CO2 tolerance which causes you to breath off too much CO2, and low CO2 levels relax smooth muscle, including the smooth muscle of your throat (which otherwise should actively maintains your airway at all times). The above two practices increase CO2 tolerance.

(Low CO2 tolerance can be caused by many things (e.g. too much mouth breathing from allergies, jobs which require lots of talking or singing or instrument playing, lots and lots of sitting without exercising, chronic anxiety, etc.)

Evidence:

1. Personal/anecdotal: Intense jaw clenching, tongue soreness, turbinate opening within a few days of starting buteyko breathing, objectively far less moving around during sleep, subjectively deeper more refreshing sleep.
2. This is how I think (poorly edited rant): http://meditationstuff.wordpress.com/2013/08/05/rant-thought-stopping-truths-e-g-weight-loss/
3. Clinical trial(s?) show that Buteyko breathing does stuff (e.g. improves asthma symptoms without increasing lung capacity)