The Carnegie Supernova Project (CSP) is designed to measure the luminosity distance for Type Ia supernovae (SNe Ia) as a function of redshift, and to set observational constraints on the dark energy contribution to the total energy content of the universe. The CSP differs from other projects to date in its goal of providing an I-band rest-frame Hubble diagram. Here, we present the first results from near-infrared observations obtained using the Magellan Baade telescope for SNe Ia with 0.1 < z < 0.7. We combine these results with those from the low-redshift CSP at z < 0.1. In this paper, we describe the overall goals of this long-term program, the observing strategy, data reduction procedures, and treatment of systematic uncertainties. We present light curves and an I-band Hubble diagram for this first sample of 35 SNe Ia, and we compare these data to 21 new SNe Ia at low redshift. These data support the conclusion that the expansion of the universe is accelerating. When combined with independent results from baryon acoustic oscillations, these data yield Omega(m) = 0.27 +/- 0.02( statistical) and Omega(DE) = 0.76 +/- 0.13( statistical) +/- 0.09(systematic), for the matter and dark energy densities, respectively. If we parameterize the data in terms of an equation of state, omega (with no time dependence), assume a flat geometry, and combine with baryon acoustic oscillations, we find that omega = -1.05 +/- 0.13( statistical) +/- 0.09( systematic). The largest source of systematic uncertainty on w arises from uncertainties in the photometric calibration, signaling the importance of securing more accurate photometric calibrations for future supernova cosmology programs. Finally, we conclude that either the dust affecting the luminosities of SNe Ia has a different extinction law (R(V) = 1.8) than that in the Milky Way (where R(V) = 3.1), or that there is an additional intrinsic color term with luminosity for SNe Ia, independent of the decline rate. Understanding and disentangling these effects is critical for minimizing the systematic uncertainties in future SN Ia cosmology studies.