In many ways this needs to be individualized. My experience has been in century type rides during the summers over the last 15 years. Most of which are in hilly and mountainous regions in Oregon and Washington. The suggestions following are what I have refined during that period based on experience and significant reading on the subject. Additionally, I work part time as a fitness trainer, and have helped others train for centuries.
During the off-season, which for me runs from November through February, my primary goals in the gym are strength, power and stability. After February, the gym work is minimal and training shifts to riding. I can't provide a complete description here, but here's a summary of my program related to climbing ability.
- Strength - The key exercises are lunges, squats and rack-pulls. These exercises utilize free weights, build strength and work the entire lower body. Additionally, since they're done with free weights, you achieve improvements in core stability and balance. In general, these are done with heavy weight, 5 reps and 3 or 4 sets. A hugely important aspect is correct form in order to avoid injury.
- Power - Power exercises are for developing explosive ability and speed. An example would be when you need an extra burst on a steep section of a hill. Also known as plyometrics. Here's a link to the basic idea: http://www.sport-fitness-advisor.com/plyometricexercises.html
- Stability - These exercises are designed to improve stability and utilize body weight and/or light weights. Split squat, medicine ball squat, single-leg Romanian deadlift, ball squat, crossover step-up, side-lying leg lifts. (FWIW - I have virtually eliminated an ITBS issue with this stability workout.) For each of these it's 3 sets, 10 reps.
Finally, during the course of the off-season I am cycling through these strength, power and stability workouts. For myself it's approximately 60% strength, 20% power, and 20% stability. How one cycles through these workouts is highly individualistic and is based on goals and one's fitness level. For example, in the last 3 weeks, I've done strength work on Monday and Friday with plyometrics on Wednesday. And next week will be 3 or 4 stability workouts.
The next planned century is in mid May. In March, I'll drop the strength and power training and move to almost exclusively to "on bike" training. The guide I follow pretty closely is The Time-Crunched Cyclist by Chris Carmichael and Jim Rutberg.
And just a note...the workout plan is not specifically and only for hill climbing. Through experience, I've found that the stronger I am going into the "season", the better I perform. Additionally, my other sports and daily living activities are improved as well.
An update...not to belabor The Time-Crunched Cyclist, but both I and riding partners have significantly improved our personal performance on hilly to mountainous century rides using Carmichael's methods. There are 3 types of intervals specific to climbing improvement. Not the full details, but a summary. Mix these into your training rides. Generally, not all three on the same day, and not on consecutive days; but these intervals once or twice a week should yield results.
Climbing Repeats - Done a long, steady climb. Staying within 78 - 80% of Max Heart Rate for the climb with a cadence of 70 - 85 rpm. This increases climbing lactate threshold. (3X, 6 minutes each, 3 minute rest between)
Hill Acceleration - On a long, moderate climb, pedal slowly until reaching the last 500 yards. Then gradually speed up so that you are at near max heart rate. Finish out of the saddle at max effort. (4X, 10 seconds, 3 minute rest between)
Hill Sprint - Roll at a moderate speed in a moderate to light gear. As you hit the hill, jump out of the saddle and go hard. Try to hold top speed. Increases power for acceleration. (4X, 10 seconds, 3 minute rest between)