I climbed the Kautz route 2 summers ago. I ran about five miles four times a week and worked up to 80 pounds in a pack on the stair climber (trying to average above 60 steps/min for an hour) about 3-5 times a week.
With running, I tried to do a lot of interval training 1-2 minute sprint followed by 1-2 minutes at a slower pace.
Being off the mountain, I'll say I remember it not being too difficult. Looking through my journal, I wrote that it was difficult, but I definitely was more prepared than everyone except one guy and the guides.
I used the same technique for training this past May when I went to Denali. I just increased the distance I ran and the weight in my pack. Denali was very hard, but once again, I was more prepared than most people. The person who was MOST prepared for Denali had a very different technique for preparation. He did crossfit 4-5 times a week and maybe an additional run once a week. Now that I'm home, I've been doing crossfit and I agree with him that it's probably the best way to prepare for mountaineering. He was better prepared than me by working out a little more than a third of the time I did.
Really, the only variable is altitude. It's never (yet) hit me hard, but I'm sure it will eventually. On Rainier, I saw a guy who's climbed more than a dozen 14k+ peaks without issue, start vomiting and have to turn back at 10,000 feet.
I think just as important as your fitness level is your mental level. Be prepared for long days of carrying a heavy pack doing little more than watching the rope in front of you. That's part of the reason I found the stairclimber helped. It was miserable and boring, so being on an awesome mountain with great views accomplishing a great goal was fun. Also, one of the guys who summited Denali on my trip just did some weekend backpacking trips, ran once in Colorado, and smoke cigarettes. He just wanted to climb Denali so bad that he sacrificed any luxury and worked overtime for over a year.
If you've never been on a guided trip, you'll be going a lot slower than you're used to. Sometimes it seems too slow, but that's what you have to do on big peaks!