In the past decade, molecular gas observations have begun probing the high redshift universe in a systematic way using increasingly powerful millimeter instruments. This work has significantly advanced our understanding of the history of gas consumption by star formation in galaxies, revealing the high redshift universe to be similar in many ways to what we know locally. Specifically, molecular gas studies suggest that at both high and low redshift, the molecular gas reservoir in galaxies is insufficient to support on-going star formation. This is the molecular gas depletion problem, and motivates the research presented in this dissertation. I first investigate the molecular gas depletion problem on cosmic scales. Using the observed cosmic densities of the star formation rate, atomic gas and molecular gas, combined with measurements of the molecular gas depletion time in local galaxies, I derive the history of gas consumption by star formation from z = 0 to z ~ 4. I show that models in which the molecular gas is not replenished, or is only replenished by atomic gas, are not consistent with observational constraints. I find that star formation on cosmic timescales must be fueled by intergalactic ionized gas at an average rate that roughly traces the star formation rate density of the universe. Further, I predict the volume averaged density of molecular gas to increase by a factor of 1.5 - 10 to z ~ 1.5 over the currently measured value, which implies that galaxies at high redshift must, on average, be more molecular gas-rich than they are at the present epoch, consistent with observations. Next I focus on the observational constraints on the molecular gas content of galaxies from z ~ 1 - 2 to today. Recent observations suggest z ~ 1 - 2 galaxies harbor molecular gas reservoirs an order of magnitude larger than their local counterparts, implying significant evolution of the molecular gas content of galaxies over the past 8 billion years. However, this period of time has been relatively un-observed in molecular gas. To fill in this observational gap, I carry out the Evolution of molecular Gas in Normal Galaxies (EGNoG) survey, a study of molecular gas in 31 star-forming galaxies from z = 0.05 to z = 0.5. With observations of the CO(1-0) and CO(3-2) rotational lines using the Combined Array for Research in Millimeter-wave Astronomy (CARMA), the EGNoG survey accomplishes two goals: tracing the evolution of the molecular gas content of galaxies at intermediate redshifts and constraining the excitation of the molecular gas in these galaxies. With 24 detections out of 31 observed galaxies, I calculate an average molecular gas fraction of 7 - 20% at z ~ 0.05 - 0.5, which is in line with observations at high and low redshift and agrees well with the evolution predicted by a simple empirical prescription for gas consumption by star formation in galaxies from z ~ 1 - 2 to today. The EGNoG observations of four galaxies at z = 0.3 (the gas excitation subsample) yield robust detections of both lines in three galaxies (and an upper limit on the fourth). I find an average line ratio, r31 = L'(CO(3-2)) / L'(CO(1-0)), of 0.46 ± 0.07 (with systematic errors less than 40%), which implies sub-thermal excitation of the CO(3-2) line. As the EGNoG galaxies are representative of the main sequence of star-forming galaxies, I extend this result to include main sequence galaxies at high redshift. To support the observations carried out at CARMA as part of the EGNoG survey, I give two appendices. The first details the data reduction and flux measurement for the EGNoG survey, including a description of the use of polarized calibrators to calibrate data from single, linearly polarized feeds. In the second appendix, I describe the absolute flux calibration of CARMA data and the automated monitoring system I helped put in place in order to maintain a historical record of the flux of common calibrators. Finally, I return to the gas depletion problem in the local universe. I carry out a pilot study of atomic (HI) gas in groups of galaxies in order to investigate the role of tidal interactions in transporting atomic gas from the outskirts of galaxy disks to the central regions so that it may replenish the molecular gas and fuel ongoing star formation. I image three groups of galaxies in the 21 cm line of HI with the Allen Telescope Array (ATA), detecting many galaxies not previously observed in HI as well as four previously undetected clouds of HI between galaxies that account for up to 3% of the HI reservoir of the groups. To investigate the potential role of this gas in the ongoing star formation in the group, I compare the mass of the detected HI gas in and between galaxies in the group to the estimated star formation rates of the group members.