While wattage is important, there are two things to consider: 1) headroom and 2) damping factor. The more watts, the cleaner the power, especially the low end, and especially at high volume.
Higher damping factor, in my opinion, is the more important of the two. A high damping factor means cleaner, clearer, and more solid bass reproduction.
A good rule of thumb is to have 50% more wattage than the sum of your cabs RMS - so, a 500 watt cab and should have at least a 750 watt amp (or channel of an amp), etc. The more the better, though, as far as headroom is concerned. You really can't hurt a cab with too MUCH power. What damages speaker cones is attempting to reproduce distorted signals. If the amp is underpowered (causing distortion), you will damage the cones very easily. Check out the peak on your cabs... it's usually 4 times the RMS or so.
I use a Crown I-Tech 4000, one channel running each of my cabs (see signature). It's 2000 watts per side and has a damping factor of about 5300 at 30 hz. Wow! Very clean, powerful, and solid low end. It's also 28 pounds and highly recommended.
Something else to consider is the cooling system. Convection cooling, which doesn't use fans, draws more consistent amperage and therefore has less fluctuation in tone, which is especially important if you're recording and micing cabs (rather than running direct). Crown K2 power amps (1200 watts/side) are great for this, or, you can just put your power amp outside the iso booth and run the speaker cables in with the cabs and the mics.