How can a CPU dynamically change its clock frequency?
The core clock of the CPU isn't received directly from the motherboard. That clock is usually much slower (often by a factor of 10 or more) than the internal frequency of the CPU. Instead, the clock signal from the motherboard is used as the reference frequency for a higher frequency phase locked loop controlled oscillator inside the CPU. The generated clock runs at some multiple of the reference clock, and that multiple can be changed by setting certain registers in the CPU. The actual generation of the clock is done purely in hardware.

To reduce power even further, the CPU also signals to the voltage regulator supplying its core voltage to run at a lower set point. At lower frequencies the CPU can run at a lower voltage without malfunctioning, and because power consumption is proportional to the square of the voltage, even a small reduction in voltage can save a large amount of power. 

The voltage and frequency scaling is done by hardware, but the decision to run in a low power mode is made by software (the OS). How the OS determines the optimal mode to run in is a separate, messier, problem, but it likely comes down to mostly what %time has the system been idle lately. Mostly idle, lower the frequency. Mostly busy, raise the frequency. Once the OS decides the frequency to run at, it's just a matter of setting a register.

Reference: "Enhanced Intel SpeedStep Technology for the Intel Pentium M Processor"