We present Keck spectroscopic observations and redshifts for a sample of 767 Herschel-SPIRE selected galaxies (HSGs) at 250, 350, and 500 mum, taken with the Keck I Low Resolution Imaging Spectrometer and the Keck II DEep Imaging Multi-Object Spectrograph. The redshift distribution of these SPIRE sources from the Herschel Multitiered Extragalactic Survey peaks at z = 0.85, with 731 sources at z < 2 and a tail of sources out to z ~ 5. By probing the dust spectral energy distribution (SED) at its peak, we estimate that the vast majority (72%-83%) of z < 2 Herschel-selected galaxies would drop out of traditional submillimeter surveys at 0.85-1 mm. We find that dust temperature traces infrared luminosity, due in part to the SPIRE wavelength selection biases, and partially from physical effects. As a result, we measure no significant trend in SPIRE color with redshift; if dust temperature were independent of luminosity or redshift, a trend in SPIRE color would be expected.