At the time, the limiting cases of the power spectrum were known via both experiment and theory. The Rayleigh-Jeans fit lower frequency radiance while the Wien fit the higher frequency (though Wien seemed to derive his equations more from empirical fitting than strong theoretical footing). The Rayleigh-Jeans distribution can be found using classical electrodynamics and classical statistical mechanics. However, as mathman stated, you end up with the ultraviolet catastrophe where the energy density suffers from an ultraviolet divergence. It was theorized at the time, by Rayleigh and others, that the fault laid in the classical equipartition theory.
Planck looked at the Wien and Rayleigh-Jeans results and proposed an interpolation between the two results. This was the same as the resulting Planck distribution. It then took him several weeks to find a physical and theoretical reasoning behind this and this was done by throwing out the classical equipartition theory and devising a new one that required the energy to be quantized. Actually, quantization of energy was done by Boltzmann as a tool for derivations but with Boltzmann the quantization did not affect the final results. However, removing the quantization in Planck's derivation simply results in the Rayleigh-Jeans distribution again. Thus, Planck's use of quantization was essential. In addition to the quantization, Planck used a different method for counting the elements which is consistent with what is now called Bose-Einstein statistics (as opposed to the Maxwell-Boltzmann statistics that gave rise to the Rayleigh-Jeans).
So basically Planck found a way to fit an equation that matched the Wien and Rayleigh-Jeans distributions and was able to a posteriori derive this distribution by using a new equipartition theorem. This matched the suspicions of other physicists at the time that the classical statistical equipartition theory may be the problem.
Milonni has a few sections in his Quantum Vacuum book that discusses this in detail.