Start with cardio and progress to weights
Start by targeting a 'moderate' heart rate to burn the fat you already have. By moderate I mean Aerobic on the chart below.
Note: Image taken from [Wikipedia] and falls under CC-SA license.
Ignore the 'Weight Control' region for a minute and bear with me. What you're targeting here is the Aerobic Zone. Why, you may ask? While the weight burning zone is good for burning fat while you work out, it isn't really optimal for weight loss because as soon as you stop your body will go back to it's normal resting heart rate.
When you do an Aerobic workout, not only will the workout burn a lot of energy itself but it will continue to burn energy for the rest of the day. Try taking your heart rate a few hours after you finish running, you'll find that it's still chugging along burning energy.
So that takes care of initially burning off the excess energy (fat) but how do you keep it off in the long term without having to go to the gym 3 times a week (for your 30-60 minute cardio run)? Build muscle mass.
I'm not talking about the Type 1 muscles that you build from doing long distance running. I'm talking about the Type 2 fast twitch muscles that use tons of energy just to maintain themselves. These are what you build with exercises like weight lifting, (some) team sports (basketball, soccer, hockey), sprinting, etc...
There are 3 ways to check your heart rate while working out:
This method is a PITA and it's nearly impossible to do while running.
I highly recommend using one of these if you have the money to burn because not only does it let you see a real time measurement but having constant feedback over a long period of time gives you a sense of how hard you should be pushing yourself while you work out
- Listen to what your body tells you
This is the best method when you first start out. The problem with the generic chart above is it assumes that you're in good health and average everything when in fact you're not (especially when you're out of shape).
The key terms you need to remember are 'aerobic' and 'anaerobic'. What these two terms mean are 'with oxygen' and 'without oxygen'. When you hit your aerobic range you start breathing harder because your body requires more oxygen to meet the performance needs of your workout. This is about the equivalent to a moderate-fast jog for somebody in good shape. The anaerobic range is when your body loses its ability to break down lactate at a fast enough rate and it starts to accumulate in your blood stream. Lactic acid is a byproduct of anaerobic metabolism and one of the reasons you feel sore the day after a hard workout. This is the stage when you find yourself gasping for air and feel your muscles burning. It's also the state you'll find yourself in when you start doing strenuous workouts.
The reason I say to feel it out when you first start is, your body is most likely in poor working shape. Because it's not used to the strain of exercise, it won't be adapted to the high demand of oxygen. You'll find yourself gasping for oxygen even on easy workouts and everything in the chart gets shifted because your VO2 max is much lower.
It takes some time for your body to adjust to exercise. It has to produce more red blood cells to carry oxygen. Drinking enough water is important for this or you'll get the workout hangover feeling. Your body also needs to cleanse itself of toxins like crap in your lungs and vascular system. It takes time for your body to fully adjust (don't rush the progression).
Listen to what your body tells you. Start out with the aerobic stuff and wait until it starts to feel easy until you introduce the harder workouts. Eventually, when you're ready you can shift over completely.
I usually start with 30-60 minute runs and after a week or two introduce a sprint. The sprint involves a mile to warm up (and to gradually get up to speed) a mile on full speed, and a mile to cool down (and gradually reduce the speed). When I say gradually increase/decrease the speed I'm talking some small increment that you use (like .5mph per 10th of a mile). Even if you're gasping after the mile at full speed force yourself to follow the gradual decreases in speed (unless you physically can't). What this does is push your anaerobic threshold even higher. A higher anaerobic threshold means you'll feel less sore and you'll be able to work out harder without feeling fatigued in the future.
At that point the workout doesn't need to get any longer (the sprints only get more difficult if you choose to push yourself). The sprint takes about 15-20 minutes to accomplish (less if I the warm-up cool-down phases are shortened) and you don't really need to do it that often for maintenance (max 2 times a week).
The benefits are, your body will naturally burn more energy because of the increase in muscle mass and if you quit for a while you still won't get chubby.
My general rule for muscle mass is, it takes 3 times longer to lose it than it took to build it (that's what I find at least). Meaning that if you work out and continue to improve over a 3 month period it'll take 9 months until you fall back into bad shape (a really bad diet can make this worse).
You may replace sprinting with lifting weights if you want but take note that it will take more time/work to maintain. Running builds muscle all throughout your body whereas lifting weights only targets individual regions. My 15-20min routine may take 1hr of lifting weights to effectively match.
As for diet, increase lean protein sources and decrease carbohydrates and fatty meats (like beef). By lean protein I'm referring to eggs, tuna, edamame, beans, chicken (if it's cooked right). Be sure not go on a protein-only diet though, a diverse diet is still important.
Another thing to make sure of is, always do cardio on an empty stomach (don't eat within 3 hours of a workout). If you're exercising in the morning, make sure you get a good meal the night before. You shouldn't need a whole lot of energy if you're not exercising for an extended period and this will force your body to burn the energy it has readily stored (fat). Save the meal for right after the workout, within 45 minutes after a workout is the period when nutrient uptake is at its greatest (and if feels the most satisfying).
As for lifting weights, if you plan to do it for an extended period of time you may need to eat before. Watch out for a feint light headed feeling (if you feel like this don't keep lifting). Light headedness is an indicator of low blood sugar so adjust your routine to eat before.
I have just realized a glaring mistake in the heart rate chart. The 'Maximum Effort' zone is not your V02 MAX. Your VO2 MAX is the point where your body's oxygen uptake reaches it's maximum so it has to fire up your anaerobic metabolism to compensate. This 'correct' classification of this would be the borderline between your aerobic and anaerobic zones.
@ldx Also had a very interesting link with a lot of good info about studies that determine the differences (results obtained) between aerobic/anaerobic exercises that should help your further optimize your workouts (I'm definitely going to try making some adjustments).