We have begun the ExploreNEOs project in which we observe some 700 Near-Earth Objects (NEOs) at 3.6 and 4.5 Delta *mm with the Spitzer Space Telescope in its Warm Spitzer mode. From these measurements and catalog optical photometry we derive albedos and diameters of the observed targets. The overall goal of our ExploreNEOs program is to study the history of near-Earth space by deriving the physical properties of a large number of NEOs. In this paper, we describe both the scientific and technical construction of our ExploreNEOs program. We present our observational, photometric, and thermal modeling techniques. We present results from the first 101 targets observed in this program. We find that the distribution of albedos in this first sample is quite broad, probably indicating a wide range of compositions within the NEO population. Many objects smaller than 1 km have high albedos (0.35), but few objects larger than 1 km have high albedos. This result is consistent with the idea that these larger objects are collisionally older, and therefore possess surfaces that are more space weathered and therefore darker, or are not subject to other surface rejuvenating events as frequently as smaller NEOs.