Current studies are showing that interval-type training/exercise is more effective for a weight loss program than steady pace cardiovascular workouts.

This, combined with an effective change in eating habits, seems like the way to lose fat and increase fitness.

http://www.cptips.com/intervl.htm