How does a CPU ever go Idle enough to enter deeper C states?

CPUs (or individual cores) can be put into "deep" C-states by an OS kernel.

You're thinking that the processor "puts itself to sleep" when it "detects" inactivity. This isn't how it works. The OS scheduler determines system idle percentage based on the amount of time spent in the system idle loop to detect system inactivity. The CPU itself (in x86 land, at least) doesn't know "what" it's executing and doesn't have context to "detect" idle cycles on its own.

The system firmware contains ACPI tables that define the power management capabilities of the hardware. These tables are read by the OS when it starts up. The OS kernel processor driver (or whatever the analog is to that for a given operating system) is responsible for monitoring the CPU workload and instructing the hardware to put the CPU into a power management state selected from the firmware ACPI tables.

Microsoft has an article describing power management in Windows 7 and Server 2008 R2. IBM has an article (likely dated, however) about the CPUfreq system in Linux.

Edit:

It's worth pointing out that many server computers have an onboard hardware-based mechanism to monitor and manage CPU states. This isn't being done "in the CPU" either, but rather is taking the place of the OS power and performance management functionality. It's been my experience that this often yields power savings but at the expense of system performance.