Just like with any other specific cycling skill set (sprinting, time trialing, etc.), climbing takes some specific work. Just being a stronger rider over all will improve your climbing, so the more miles you have in your legs the less the grades will affect you.
The best way I've found to get my climbing legs is exactly the same way I get my general cycling legs in the early spring. Start with long sustained efforts on a long climb, well within capabilities. Think of this as your climbing base miles. Since climbing puts a different stress on the legs than hard riding on the flats, these efforts are essential. Then go to some medium length harder efforts. These are your tempo efforts on the hills. They let you ride comfrotably at a hard pace so you can stay with the front group. Finally, some uphill out of the saddle attacking efforts will put the finishing touches on your climbing. These will let you stay with attacks or launch your own.
Also, don't forget to train on different types of hills. Long and gradual, short and steep, etc.
Get a cheap HR monitor. Find your max heartrate. Then train at 80% of your max heartrate for an hour or so. You'll basically be training at your lactate threshold, which is pretty much where your heart rate falls when you ride in the mountains. This will improve your endurance for longer climbs and time trials as well.
But, I would note that doing this type of training is hard on the body, and you should definitely space these type of workouts around rest days.
Now I am not a pro, nor a sports physician, but I do think analysis of pro cyclists data can give you a good insight in how to train. First of all, and therewith risking to state the obvious, Merckx expressed it most eloquently, namely that you get good at what you do a lot. If you want to be a good climber, climbing hills or mountains is the best way to go.
Secondly and more concretely, I think interval trainings are most beneficial, as they give quick results in a relatively low time-consuming way. The problem then is, what kind of intervals should you do?
If you do have hills or mountains in your area, it's fairly easy, so I would suggest doing intervals (3 reps of 6 mins to 6x6 on / every rep followed by an off dependent on your fitness level) 2 to 3 times a week. Cadence around 60-70 and heart rate 95%.
On the other hand, most of us don't live near mountains or long enough hills so you will want to simulate climbing conditions throughout your intervals. During wintertime you can do this wondefully on your indoor trainer. I'd recommend doing 3x6 to 6x6 mins on / off depending on your fitness level, on high gear and low cadence. You need to push hard similar to what you would feel doing high rep leg presses to rotate and get a high heart rate. Again aim for low cadence 60-70 and high heart rate.
I think the following charts are pretty instructive, mostly because they are are from one of the best young climbers in the peloton.
You have to keep in mind that if you are trying to improve your climbing that there is technique and that there is specific training that can be done. I do agree that intervals are a great way to increase your lactate threshold which will make you stronger. I dont agree that you should work at 95% at a cadance of 60-70. Gesink is a pro rider, and if you are not or are not used to training at this level then your body is not going to respond well to that effort. You have to build up to it.
Here are some relevant articles for you to check out that will help. I have been under the supervision of a coach for a few years and that has by far been the greatest tool in making me a better climber.
Losing weight is a super effective way to improve your climbing. Not being facetious here. Don't overlook the obvious. Also, drink lots of water. Like lots. Will make you ride faster, and recover faster.
Training? 6 * 30s on 30s off, 6 minute rest, 3 sets. 30 seconds should basically be an uphill sprint. These should hurt like hell. Do these right and you'll get retardedly fast.