We present the Evolution of molecular Gas in Normal Galaxies (EGNoG) survey, an observational study of molecular gas in 31 star-forming galaxies from z=0.05 to z=0.5, with stellar masses of (4-30)x10^10 M_Sun and star formation rates of 4-100 M_Sun yr^-1. This survey probes a relatively un-observed redshift range in which the molecular gas content of galaxies is expected to have evolved significantly. To trace the molecular gas in the EGNoG galaxies, we observe the CO(1-0) and CO(3-2) rotational lines using the Combined Array for Research in Millimeter-wave Astronomy (CARMA). We detect 24 of 31 galaxies and present resolved maps of 10 galaxies in the lower redshift portion of the survey. We use a bimodal prescription for the CO to molecular gas conversion factor, based on specific star formation rate, and compare the EGNoG galaxies to a large sample of galaxies assembled from the literature. We find an average molecular gas depletion time of 0.76 pm 0.54 Gyr for normal galaxies and 0.06 pm 0.04 Gyr for starburst galaxies. We calculate an average molecular gas fraction of 7-20% at the intermediate redshifts probed by the EGNoG survey. By expressing the molecular gas fraction in terms of the specific star formation rate and molecular gas depletion time (using typical values), we also calculate the expected evolution of the molecular gas fraction with redshift. The predicted behavior agrees well with the significant evolution observed from z~2.5 to today.