The detection of spectral variability of the gamma-ray blazar Mrk 421 at TeV energies is reported. Observations with the Whipple Observatory 10m gamma-ray telescope taken in 2000/2001 revealed exceptionally strong and long-lasting flaring activity. Flaring levels of 0.4 to 13 times that of the Crab Nebula flux provided sufficient statistics for a detailed study of the energy spectrum between 380 GeV and 8.2 TeV as a function of flux level. These spectra are well described by a power law with an exponential cutoff. There is no evidence for variation in the cutoff energy with flux, and all spectra are consistent with an average value for the cutoff energy of 4.3 TeV. The spectral index varies between 1.89 in a high flux state and 2.72 in a low state. The correlation between spectral index and flux is tight when averaging over the total 2000/2001 data set. Spectral measurements of Mrk~421 from previous years (1995/96 and 1999) by the Whipple collaboration are consistent with this flux-spectral index correlation, which suggest that this may be a constant or a long-term property of the source. If a similar flux-spectral index correlation were found for other gamma-ray blazars, this universal property could help disentangle the intrinsic emission mechanism from external absorption effects.