We have measured K-band surface brightness fluctuations (SBFs) of 19 early-type galaxies in the Fornax cluster. Combining our results with published data, we find the absolute SBF magnitude Mbar_K = (-5.84)+(3.6)*[(V-I)-1.15]. The intrinsic cosmic scatter of Mbar_K appears to be larger than that of I-band SBFs. The discovery of a correlation between K-band SBFs and V-I color is a new clue into the star formation histories of early-type galaxies. This relation naturally accounts for galaxies previously claimed to have anomalously bright K-band SBFs, namely M32 and NGC 4489. Models indicate that the stellar populations dominating the SBF signal have a significant range in age; some scatter in metallicity may also be present. The youngest ages imply some galaxies have very luminous giant branches, akin to those in intermediate-age (few Gyr) Magellanic Cloud clusters. A few Fornax galaxies have unusually bright K-band SBFs, perhaps originating from a high metallicity burst of star formation in the last few Gyr. The increased spread and brightening of the K-band SBFs with bluer (V-I) colors suggest that the lower mass cluster galaxies may have had more extended and more heterogeneous star formation histories than those of the more massive galaxies. (Abridged)

Astrophysical Journal, in press (24 pages). Uses emulateapj5.sty. V3 has a cosmetic change to Figure 7. V4 corrects some minor typos