We have obtained spectroscopic redshifts using the Keck-I telescope for a sample of 73 submillimeter (submm) galaxies for which precise positions are available. The galaxies lie at redshifts out to z=3.6, with a median redshift of 2.2. The dust-corrected ultraviolet (UV) luminosities of the galaxies rarely hint at their huge bolometric luminosities indicated by their radio/submm emission, underestimating the true luminosity by a median factor of ~100 for SMGs with pure starburst spectra. The 850mu, radio, and redshift data is used to estimate the dust temperatures (=36+-7 K), and characterize photometric redshifts. We calculate total infrared and bolometric luminosities, construct a luminosity function, and quantify the strong evolution of the submm population across z=0.5-3.5, relative to local IRAS galaxies. We conclude that bright submm galaxies contribute a comparable star formation density to Lyman-break galaxies at z=2-3 and including galaxies below our submm flux limit this population may be the dominant site of massive star formation at this epoch. The rapid evolution of submm galaxies and QSO populations contrasts with that seen in bolometrically lower luminosity galaxy samples selected in the restframe UV, and suggests a close link between submm galaxies and the formation and evolution of the galactic halos which host QSOs. [Abridged].