Mudmonkey also made a very good point; "grace" (i.e. the ability to move through a cave environment with minimal wasted energy/effort) is learned only through experience and what are known as "engrams" (similar to climbing, martial arts and dance) or "patterns of movement".
Once you have good automatic movement through a cave environment you don't necessarily need to be super-fit (although it always helps to have reserves of energy in the event of unforseen circumstances arising); so a training programme for caving would probably HAVE to include a lot of caving - since this is going to be the quickest and best way to learn this important energy-saving technique.
A second best would be to use indoor climbing walls (or outdoor real walls) and do lots of traversing or put opposing elements in (i.e. real wall with large stones placed a metre away from the wall at regular intervals and then use the wall and the stones as a representation of an underground traverse/streamway and practice moving along carrying tackle bag on back/off harness, over one arm or the other etc..).
BTW I know of "hard" cavers who regularly do triathlons, "Iron Man" and such like stuff; I don't run marathons (and couldn't!) but this doesn't mean I can't be useful underground. However, if you meet someone who is super-fit and who has never been caving you'll usually find they have no problem keeping up whatsoever; the "dangerous" people you take underground are the ones who are unfit in the first place and who end up being at risk of just sitting down totally exhausted and claiming to be unable to go any further (these people should always be taken on very easy, low-objective, trips until they start to get more fit). It's worth remembering that even a simple caving trip often equates to doing an entire 90min rugby game without a break!
