We present new Herschel-SPIRE imaging spectroscopy (194-671 microns) of the bright starburst galaxy M82. Covering the CO ladder from J=4-3 to J=13-12, spectra were obtained at multiple positions for a fully sampled ~ 3 x 3 arcminute map, including a longer exposure at the central position. We present measurements of 12CO, 13CO, [CI], [NII], HCN, and HCO+ in emission, along with OH+, H2O+ and HF in absorption and H2O in both emission and absorption, with discussion. We use a radiative transfer code and Bayesian likelihood analysis to model the temperature, density, column density, and filling factor of multiple components of molecular gas traced by 12CO and 13CO, adding further evidence to the high-J lines tracing a much warmer (~ 500 K), less massive component than the low-J lines. The addition of 13CO (and [CI]) is new and indicates that [CI] may be tracing different gas than 12CO. No temperature/density gradients can be inferred from the map, indicating that the single-pointing spectrum is descriptive of the bulk properties of the galaxy. At such a high temperature, cooling is dominated by molecular hydrogen. Photon-dominated region (PDR) models require higher densities than those indicated by our Bayesian likelihood analysis in order to explain the high-J CO line ratios, though cosmic-ray enhanced PDR models can do a better job reproducing the emission at lower densities. Shocks and turbulent heating are likely required to explain the bright high-J emission. ; Comment: Accepted to The Astrophysical Journal. 17 pages + 20 pages of appendix figures