I was a personal trainer in Daytona Beach before I moved back to Michigan and got fat and lazy.
Run... Run a few times a week, Don't smoke cigarettes. The better shape your lungs are in, and your cardiovascular system, the better athlete you will be in the water.
This isn't something that you hear a lot about, but it is probably the most important thing you can do to orient yourself to any water sport, or any sport.
I recommend running every morning (morning if possible, too complicated to explain why mornings are best in a couple sentences, but it is the best time to do aerobic exercise) Pick out a path, or a route that will take you a half hour to run, and run it, once you can run it in less than a half hour, it is time to expand your route. 45 minutes is better, but a half hour works almost just as good.
Predive stretches are a good idea too, don't overdo the stretches, just make sure you stretch out all of your muscles pretty good.
A couple good exercises in the gym are (do them like once a week, or week and half):
Squats
Quad Extensions and Hamstring Curls
Sit Ups, NOT CRUNCHES!!! The idea of a crunch is to build your abdominals so they stick out, not to add any significant stength to your midsection. (which is the most important part of your body for any sport).
It sounds like everyone else covered the in the water stuff...
Your Scuba instructor will definately cover the important stuff.
But at the very least, you should run every other day, if not more, just for a half hour.
Another thing to consider is your nutrition....
I won't go too deep into this, but your body runs off whatever fuel you put in it... Check out the book Total Nutrition if you want to know more about that.
I can feel the difference in my ability level in the water and my alertness when I am eating right and working out compared to when I am living off "Scuba Food."
Scuba Food: Anything from the gas station.