Why does a faster clock require more power?
Voltage required is affect by significantly more than clock speed, but you are correct, for higher speeds you will need higher voltages in general.
Why does power consumption increase?
This is a lot messier than a simple circuit, but you can think about it being similar to an RC circuit.
RC circuit equivilent
At DC an RC circuit consumes no power. At a frequency of infinity, which is not attainable, but you can always solve this theoretically, the capacitor acts as a short and you are left with a resistor. This means you have a simple load. As frequency decreases the capacitor stores and discharges power causing a smaller amount of power dissipated overall.
What is a microcontroller?
Inside it is made up of many many MOSFETs in a configuration we call CMOS.
If you try to change the value of the gate of a MOSFET you are just charging or discharging a capacitor. This is a concept I have a hard time explaining to students. The transistor does a lot, but to us it just looks like a capacitor from the gate. This means in a model the CMOS will always have a load of a capacitance.
Wikipedia has an image of a CMOS inverter I will reference.
The CMOS inverter has an output labeled Q. Inside a microcontroller your output will be driving other CMOS logic gates. When your input A changes from high to low the capacitance on Q must be discharged through the transistor on bottom. Every time you charge a capacitor you see power use. You can see this on wikipedia under power switching and leakage.
Why does voltage have to go up?
As you voltage increases it makes it easier to drive the capacitance to the threshold of your logic. I know this seems like a simplistic answer, but it is that simple.
When I say it is easier to drive the the capacitance I mean that it will be driven between the thresholds faster, as mazurnification put it:
With increased supply drive capability of the MOS transistor also increases (bigger Vgs). That means that actual R from RC decreases and that is why gate is faster.
In relation to power consumption, due to how small transistors are there is a large leakage through the gate capacitance, Mark had a bit to add about this:
higher voltage results in higher leakage current. In high transistor count devices like a modern desktop CPU leakage current can account for the majority of power dissipation. as process size gets smaller and transistor counts rise, leakage current becomes more and more the critical power usage statistic.
In general, CMOS gates only use current when they switch states. So the faster the clock speed is, the more often gates are switching, thus more current is switched, and more power is consumed.
Well, it's all about logic level transitions.
When any single bit of an output changes... the electrical value must slew from high to low, or low to high. This pulls power from the power supply, or dumps some power back onto the ground plane. It also generates a little waste heat due to inefficiencies.
If you increase the clock rate, you increase the number of these transitions per unit time, therefore you use more power to feed these logic level transitions.
Increased voltage requirements are a little different. The time it takes a signal to transition from low to high is called the rise time. To safely operate at any given frequency the logic must be able to consistently make this transition before the next clock samples the new value. At a certain point, the logic will not be able to meet the rise time requirements of a particular frequency. This is where upping the voltage will help, as it decreases rise time.
Heat is fairly simple. The chip is designed to handle a certain amount of heat generated by a certain clock rate. Increase the number of transitions by increasing the clock rate, and you're going to get more waste heat. When overclocking, you can easily outpace the cooling system's ability to remove that heat.