Basically what you want to do is to get stronger – you want to be able to ride in a higher gear at the same cadence. There are a number of ways to work on this, one is to push yourself hard(er) on hills.
What has worked for me is to find a hill that feels relatively easy in a low gear (for me this means that I can comfortably ride the hill at around 80 rpm). Then I'll try the hill in a higher gear (a cog or two higher in the rear, still using the small ring in front), pushing myself to keep my cadence up. I'll do this until my legs and/or lungs hurt, then I'll coast down the hill and recover. Then I'll do it again. Maybe four or five times. Then I'll go for a nice ride :-)
I think the formal name for it is something like interval training or hill repeats. The idea is to work yourself hard enough to get your heart rate high and trigger release of growth hormone. The growth hormone tells your body that it needs more muscle. It must figure out somehow that the tired muscles are the ones to grow…
The weight of your bike, is a mixed blessing – for absolute performance it definitely hurts – it's more weight that you have to carry up the hill, but on the other hand that same extra weight is helping you get stronger. I'm sure someone knows how to do the calculations, but my gut sense is that it is not a huge difference.