Continuing the observational campaign initiated by our group, we present the long term spectral evolution of the Galactic black hole candidate Cygnus X-1 in the X-rays and at 15GHz. We present about 200 pointed observations taken between early 1999 and late 2004 with the Rossi X-ray Timing Explorer and the Ryle radio telescope. The X-ray spectra are remarkably well described by a simple broken power law spectrum with an exponential cutoff. Physically motivated Comptonization models, e.g., by Titarchuk (1994ApJ...434..570T, compTT) and by Coppi (1999, eqpair), can reproduce this simplicity; however, the success of the phenomenological broken power law models cautions against ``over-parameterizing'' the more physical models. Broken power law models reveal a significant linear correlation between the photon index of the lower energy power law and the hardening of the power law at about 10keV. This phenomenological soft/hard power law correlation is partly attributable to correlations of broad band continuum components, rather than being dominated by the weak hardness/reflection fraction correlation present in the Comptonization model. Specifically, the Comptonization models show that the bolometric flux of a soft excess (e.g., disk component) is strongly correlated with the compactness ratio of the Comptonizing medium, with L_disk{propto}(l_h_/l_s_)^-0.19^. Over the course of our campaign, Cyg X-1 transited several times into the soft state, and exhibited a large number of ``failed state transitions''. The fraction of the time spent in such low radio emission/soft X-ray spectral states has increased from about 10% in 1996-2000 to about 34% since early 2000. We find that radio flares typically occur during state transitions and failed state transitions (at l_h_/l_s_~3), and that there is a strong correlation between the 10-50keV X-ray flux and the radio luminosity of the source. We demonstrate that rather than there being distinctly separated states, in contrast to the timing properties the spectrum of Cyg X-1 shows variations between extremes of properties, with clear cut examples of spectra at every intermediate point in the observed spectral correlations.