We describe the CO Luminosity Density at High-z (COLDz) survey, the first spectral line deep field targeting CO(1-0) emission from galaxies at z = 1.95-2.85 and CO(2-1) at z = 4.91-6.70. The main goal of COLDz is to constrain the cosmic density of molecular gas at the peak epoch of cosmic star formation. By targeting both a wide (∼51 arcmin2) and a deep (∼9 arcmin2) area, the survey is designed to robustly constrain the bright end and the characteristic luminosity of the CO(1-0) luminosity function. An extensive analysis of the reliability of our line candidates and new techniques provide detailed completeness and statistical corrections as necessary to determine the best constraints to date on the CO luminosity function. Our blind search for CO(1-0) uniformly selects starbursts and massive main-sequence galaxies based on their cold molecular gas masses. Our search also detects CO(2-1) line emission from optically dark, dusty star-forming galaxies at z > 5. We find a range of spatial sizes for the CO-traced gas reservoirs up to ∼40 kpc, suggesting that spatially extended cold molecular gas reservoirs may be common in massive, gas-rich galaxies at z ∼ 2. Through CO line stacking, we constrain the gas mass fraction in previously known typical star-forming galaxies at z = 2-3. The stacked CO detection suggests lower molecular gas mass fractions than expected for massive main-sequence galaxies by a factor of ∼3-6. We find total CO line brightness at ∼34 GHz of 0.45 ± 0.2 μK, which constrains future line intensity mapping and CMB experiments.