We present the design and methods of the COS-Halos survey, a systematic investigation of the gaseous halos of 44 z = 0.15-0.35 galaxies using background QSOs observed with the Cosmic Origins Spectrograph aboard the Hubble Space Telescope. This survey has yielded 39 spectra of z em sime 0.5 QSOs with S/N ~10-15 per resolution element. The QSO sightlines pass within 150 physical kpc of the galaxies, which span early and late types over stellar mass log M */M ☉ = 9.5-11.5. We find that the circumgalactic medium exhibits strong H I, averaging sime 1 Å in Lyα equivalent width out to 150 kpc, with 100% covering fraction for star-forming galaxies and 75% covering for passive galaxies. We find good agreement in column densities between this survey and previous studies over similar range of impact parameter. There is weak evidence for a difference between early- and late-type galaxies in the strength and distribution of H I. Kinematics indicate that the detected material is bound to the host galaxy, such that gsim 90% of the detected column density is confined within ±200 km s–1 of the galaxies. This material generally exists well below the halo virial temperatures at T lsim 105 K. We evaluate a number of possible origin scenarios for the detected material, and in the end favor a simple model in which the bulk of the detected H I arises in a bound, cool, low-density photoionized diffuse medium that is generic to all L* galaxies and may harbor a total gaseous mass comparable to galactic stellar masses.