Hikes-with-him,
Rather than tell you what to do, I'll tell you what does and doesn't work for me.
Weight lifting: Upper body, I do it for vanity. Doesn't help me one bit with regards to hiking. I want to look good (well, not good, but at least less bad) in jeans and a t-shirt. Vanity plain and simple. Lower body, huge hiking benefit. Lower body workout with weights has helped big time on uphills but even more on down hills. Also has helped reduce knee pain (stronger muscles surrounding the knee helps alot).
Strengthening the core (abs, back, and butt): obvious benefits
Mental toughness: Just another phrase for masochism. I work out in my garage....85 in the summer, 35 in the winter....I hate gyms, too much wasted time for me (driving there and back, waiting for the machines, weights, not to mention the crappy music and the guidos, etc). It can be (gradually) taught/learned, just ask any Marine Corps drill instructor.
Stairmaster: Tried it a few times, hurts my knees.
Biking: Never considered it exercise, probably because of where I lived, too flat and not enough open space. Plus the seats always hurt my junk.
Running: Great for hiking. I need to do it more. I like to mix jogging with sprinting on the same run.
Stairs: Without a doubt THE best training for hiking is when I visit the 9-story building near my house. My pack is about 20-25 pounds. Going up the stairs is a no-brainer, but going down the stairs has helped me more than any other excercise I've done (for hiking). Going up mountains has always been "easy" for me; going down has always sucked. Stair workouts have helped me immensely.
Blue Hills: Whites are too far for every weekend, but the Blue Hills have some very steep (but short) spots. I try to punish myself on those spots by going up and down repeatedly. I often carry rocks on the way up and dump them at the top (if the blue hills are getting higher it's partly my fault).
Listening to my body: Always room for improvement, but in general if my muscles and lungs burn, I keep doing it. If my joints hurt, I stop doing it.
Eating: Minimize the amount of crap I eat. Five minutes of stupidity in the kitchen can negate a great 45 minute workout.
30-40 pounds on a non-solo winter day hike seems like alot. Like others have said, you're probably humping too much stuff.