We have found a new similarity solution that describes the evolution of a supernova remnant expanding into a cloudy interstellar medium. The solution incorporates a reasonable model of the conductive evaporation of cold clouds embedded in the hot gas behind the shock. The conduction is assumed to be saturated in the evaporative flows around the clouds, which is the case for most supernova remnants (SNRs) younger than approximately 20,000 years old; previous analytical solutions to this problem are only applicable to remnants older than those usually observable at X-ray, optical, and radio wavelengths. The model has two new parameters in addition to those describing the usual Sedov solution for a uniform interstellar medium. We calculate the X-ray, infrared, and optical luminosities of remnants with evaporating clouds, and we also discuss some of the expected spectral characteristics in the various wavebands. Plausible choices for the model parameters produce remnants that are strikingly different from ordinary shell-like supernova remnants; in particular, the effects described here may explain the class of remnants observed to have centrally peaked X-ray emission and shell-like radio emission. Substantial H-alpha emission is expected from evaporating clouds, although it may not dominate the total H-alpha luminosity. We hope to learn more about both supernova remnant evolution and the structure of the interstellar medium from studying this class of remnants.