We present the most extensive analysis of Fourier-based X-ray timing properties of the black hole binary Cygnus X-1 to date, based on 12 years of bi-weekly monitoring with RXTE from 1999 to 2011. Our aim is a comprehensive study of timing behavior across all spectral states, including the elusive transitions and extreme hard and soft states. We discuss the dependence of the timing properties on spectral shape and photon energy, and study correlations between Fourier-frequency dependent coherence and time lags with features in the power spectra. Our main results follow. (a) The fractional rms in the 0.125–256 Hz range in different spectral states shows complex behavior that depends on the energy range considered. It reaches its maximum not in the hard state, but in the soft state in the Comptonized tail above 10 keV. (b) The shape of power spectra in hard and intermediate states and the normalization in the soft state are strongly energy-dependent in the 2.1–15 keV range. This emphasizes the need for an energy-dependent treatment of power spectra and a careful consideration of energy- and mass-scaling when comparing the variability of different source types, e.g., black hole binaries and AGN. PSDs during extremely hard and extremely soft states can be easily confused for energies above ~5 keV in the 0.125–256 Hz range. (c) The coherence between energy bands drops during transitions from the intermediate into the soft state but recovers in the soft state. (d) The time lag spectra in soft and intermediate states show distinct features at frequencies related to the frequencies of the main variability components seen in the power spectra and show the same shift to higher frequencies as the source softens. Our results constitute a template for other sources and for physical models for the origin of the X-ray variability. In particular, we discuss how the timing properties of Cyg X-1 can be used to assess the evolution of variability with spectral shape in other black hole binaries. Our results suggest that none of the available theoretical models can explain the full complexity of X-ray timing behavior of Cyg X-1, although several ansatzes with different physical assumptions are promising.