This is one of my favorite topics...get ready to read
Well, I did the irresponsible thing and i am writing a response without reading the whole thread. Dont kill me if i say the same stuff people said earlier
.
Cardio is obviously the most important. I have experimented quite a bit to see what helps the most with hiking. When i was a varsity distance runner and really competitive, i would still perform at (relatively) the same level as a friend who walked in the woods all the time. I was in amazing shape (about 5'10", 145, no fat, threw down 17 min 5ks on hilly courses, and could crank out sub 445 minute mile reps, etc). This other guy walked about 4 miles a day with a heavy pack on, and he performed almost at the same level as me. Cutting to the chase, if i had access to a stair stepper i would work it with a pack on (ive done worse in a gym, ie pull ups on a bar with ice axes...). Also, dont throw away lifting wieghts. I have been working out like a maniac for a good 8 months now (just for kicks, i am a fitness fiend so i wanted to try something new). I was doing heavy reps for weight gain, and pyramid lifting for overall strength. Now, i am 5'11", 180, very little fat (i still run about 7 miles every day at about 630 mile pace). I have performed better overall hiking i think than my track days. However, i know that it takes a lot of time to work out and keep peak fitness in any form. So, to hit your goal of hiking hard and long, than i suggest stairstepping (indoors) with a pack, also climbing stairs with a pack is good (because you can also practice coming down). THe best would be hike more, but keep your cardio going, and dont neglect total body strength, because it helps you in whatever form of fitness you are trying to achieve. Try to at least do push ups, sit ups, and supermans if nothing else on top of some form of cardio. That should suffice.
Edit: just read sierra's post, and i was intrigued. When I ran on the team (i dont anymore, i do my own thing) my coach would say "pain is temporary, pride is forever". This was to keep us mentally motivated during a run. You can transfer this over to hiking, a little less corny of course. Think of the views from the top, not that you are stair stepping below treeline.
this is a good site, that is pretty intense but has good advice for lifting. its honest too.
Good workout site