The Gemini Deep Deep Survey (GDDS) is an ultradeep (K < 20.6 mag, I < 24.5 mag) redshift survey targeting galaxies in the "redshift desert" between z=1 and z=2. The primary goal of the survey is to constrain the space density at high redshift of evolved high-mass galaxies. We obtained 309 spectra in four widely separated 30 arcmin2 fields using the Gemini North telescope and the Gemini Multi-Object Spectrograph (GMOS). The spectra define a one-in-two sparse sample of the reddest and most luminous galaxies near the I-K versus I color-magnitude track mapped out by passively evolving galaxies in the redshift interval 0.8 < z < 1.8. This sample is augmented by a one-in-seven sparse sample of the remaining high-redshift galaxy population. The GMOS spectrograph was operating in a nod-and-shuffle mode, which enabled us to remove sky contamination with high precision, even for typical exposures times of 20–30 hr per field. The resulting spectra are the deepest ever obtained. In this paper we present our sample of 309 spectra, along with redshifts, identifications of spectral features, and photometry. This makes the GDDS the largest and most complete infrared-selected survey probing the redshift desert. The seven-band (VRIzJHKs) photometry is taken from the Las Campanas Infrared Survey. The infrared selection means that the GDDS is observing not only star-forming galaxies, as in most high-redshift galaxy surveys, but also quiescent evolved galaxies. In our sample we have obtained 225 secure redshifts, 167 of which are in the redshift interval 0.8 < z < 2. About 25% of these show clear spectral signatures of evolved (pure old, or old + intermediate-age) stellar populations, while 35% show features consistent with either a pure intermediate-age or a young + intermediate-age stellar population. About 29% of the galaxies in the GDDS at 0.8 < z < 2 are young starbursts with strong interstellar lines. A few galaxies show very strong poststarburst signatures. Another 55 objects have less secure redshifts, 31 of which lie in the redshift interval 0.8 < z < 2. The median redshift of the whole GDDS sample is z = 1.1. Spectroscopic completeness varies from a low of ~70% for red galaxies to greater than 90% for blue galaxies. In this paper we also present, together with the data and catalogs, a summary of the criteria for selecting the GDDS fields, the rationale behind our mask designs, an analysis of the completeness of the survey, and a description of the data reduction procedures used. All data from the GDDS are publicly available.