Although fitness doesn't hurt, especially in currents or anywhere where you are having to WORK to dive, it's not really the thing that will make the biggest change in your air consumption. That thing is efficiency.
One of the biggest problems that relatively new divers have is instability. This comes from several sources:
1. It takes time to learn to balance that big, negative keel on your back. This is more noticeable with steel tanks, and especially with big ones, because at the beginning of the dive, they are quite negative. Get the least bit off to one side, and that tank just wants to keep going. Especially if the new diver is using a BC that doesn't fit real well, it's very easy for the tank to get out of the middle of the diver's back and begin to cause issues. This rotational instability results in a lot of hand-waving.
2. Buoyancy control is not mastered in a day, or a handful of dives. New divers tend to be adjusting their BCs a lot, especially if they are diving in cold water with big steel tanks. Big steels are, as I already said, quite negative at the beginning of the dive, which means you have a fair amount of air in your BC or dry suit to compensate for that gas, and that's a big air bubble to manage, especially on shallow dives. In addition, the gut-level reflex to vent or add air to something isn't solid yet, so new divers often react to buoyancy problems with a lot of hand movement, before they remember to adjust their buoyancy. Either that, or they end up swimming down against a buoyant BC or suit, which is hard work.
3. If you are diving gear that is new to you all the time, you haven't had the chance to figure out how to distribute your weight to make you horizontally stable, so you may have a pitch problem. What this means is that you can't STOP, because if you do, you will tilt feet or head down. This means you have to swim all the time, and that uses up air faster.
4. Quite frequently, especially in cold water, the large amount of weight that is required is massed too low on the diver's body. When you combine that with the fact that many new divers just don't want to flatten out, but like to keep their hip joints flexed, you have a strong tendency to dive head up/feet low. If you think about it, that has two issues that come with it: One, you are presenting a large surface area to the water, when you are trying to move forward, compared with the small profile you have if you are perfectly horizontal. Two, and more pernicious, is that if you kick, you are simultaneously driving yourself forward and UPWARD. To avoid rising in the water column, you have to keep yourself negative. This means that some portion of the work you are doing underwater is being done to create no net displacement at all, and that's just wasted muscle activity and wasted gas.
5. In order to fight all those destabilizing forces, new divers frequently want to swim fast, because strong forward motion, just like with a bicycle, tends to produce less wobbling. (The flip side of this is the new diver whose kicking technique is so inefficient that he doesn't go anywhere, despite a ton of leg activity.)
6. Instability is an insecure feeling, and this is the source of a lot of the anxiety or discomfort that new divers feel underwater. Anxiety produces an inefficient breathing pattern, consisting of rapid, shallow breaths. Since the only air that helps get rid of CO2, or deliver oxygen to the blood, is the air that gets down into the small air sacs in the lung, the air that ventilates the trachea and major bronchi does you very little good -- and when you take rapid, shallow breaths, most of the air is just exchanged in the big airways. Learning to relax and take longer, slower breaths improves gas exchange, and means you move less total volume through your lungs in any given period of time. But telling people to dive a lot and relax is really not productive, unless you help them understand WHY they are not relaxed, and what they can do about it.