So far I have climbed Rainier and Denali (which both felt pretty moderate to me, in terms of physical exertion with my legs) and am usually the guy charging out in front with a heavy pack - the steeper the slope the better. For aerobic and leg conditioning I rely on a triad of road cycling, swimming, and the stairmaster.
Road cycling is the easiest to do because it is certainly the most fun, and it really works the quadriceps. However, it works slightly different muscle groups than what you use for actual steep hiking and snowclimbing and does nothing for strengthening stabilizing muscles or training balancing your body and pack weight over your feet, so keep in mind that strength gains from cycling only have an approximate cross-over. For example, I can exhaust my legs for cycling but then have plenty of reserve to hike up steep snow and trails (makes for a great training combination!). Another downside is that unless you do nothing but sets on really steep hills (e.g. 15-20% hills), it's not very time efficient.
Swimming is something that I rarely hear other climbers doing, but I think it can be useful to include in a workout regimen. I always do flutter kick drills and distance free-style (e.g. 1-mile to 2,000 yard set). First, I've found it as a reliable fall back option to cycling on bad weather days or if I can't get out early enough to avoid cycling in the dark. Working on a hard and consistent flutter kick better trains muscles used for kicking (think kick-stepping in the snow) than running, cycling, stairs, etc. Also, it works just about every muscle in your body so is excellent for strengthening stabilizing muscles and your core and arms at the same time. Finally, by having more limited breaths, it can be helpful psychologically to be used to exercising without an ability to breath faster to make up for increased effort.
I've found the Stairmaster to be helpful if done in the right way and also realizing its limitations. When I used to live in Salt Lake City I would speed hike steep trails, sometimes with a weighted pack. In Berkeley the hills aren't steep enough, sustained enough, or long enough to make this worthwhile, so as much as it sucks, the stairmaster with a weighted pack still seems useful if done in the right way.
First, I usually wear my stiff boots to maintain the thick skin on my feet, so I never have to break my boots in for the season. I never use the handrails, forcing me to rely entirely on balancing my weight on my feet. By doing this, I'm working out my back, core, and a lot of the stabilizing muscles in addition to my quadriceps and upper calves. However, you do miss out on training strength, endurance, and stability in your ankles for the sloped surfaces and rougher trails (apart from hiking, I've found trail running to be the best for this).
Second, I set up some metrics to focus on to make sure I punish myself so that I am near exhaustion near the end and ideally near my lactic acid threshold throughout (easy to watch with a heart rate monitor). With whatever weight I have on my back, I attempt to maintain at least a 3,000 ft / hr ascent rate (it's easier to climb faster with a flat foot surface and little ankle flexure), starting at sustaining this for a minimum of 30 minutes and gradually increasing time once I increase the weight enough. I also keep track of my previous pace and try to match or improve on it, but using the 3,000 ft/hr metric as a bare minimum to meet. I also wear a regular weight that I gradually increase (up to 55 lbs right now) as my pace gets faster and it gets easier to complete the time.