In recent years, surveys at (sub)mm wavelengths have revealed a population of massive, dust-enshrouded galaxies undergoing intense bursts of star formation in the early Universe. Constraining the redshift distribution of this population, and subsequently the evolution of the obscured star formation rate at high-redshift, has been a major focus of follow-up studies of these objects. I will summarize some of the methods currently being used to measure redshifts for these (sub)mm galaxies, as well as present new evidence for a high-redshift population at z>3. Finally, I will present the results of a GBT search for CO line emission in a (sub)mm galaxy identified in the Hubble Deep Field, in order to confirm a proposed member of this z>3 population.