We employ the first two years of data from the near-infrared, high-resolution SDSS-III/APOGEE spectroscopic survey to investigate the distribution of metallicity and α-element abundances of stars over a large part of the Milky Way disk. Using a sample of ≈10, 000 kinematically unbiased red-clump stars with ~5% distance accuracy as tracers, the [α/Fe] versus [Fe/H] distribution of this sample exhibits a bimodality in [α/Fe] at intermediate metallicities, –0.9 < [Fe/H] <–0.2, but at higher metallicities ([Fe/H] ~+0.2) the two sequences smoothly merge. We investigate the effects of the APOGEE selection function and volume filling fraction and find that these have little qualitative impact on the α-element abundance patterns. The described abundance pattern is found throughout the range 5 < R < 11 kpc and 0 < |Z| < 2 kpc across the Galaxy. The [α/Fe] trend of the high-α sequence is surprisingly constant throughout the Galaxy, with little variation from region to region (~10%). Using simple galactic chemical evolution models, we derive an average star-formation efficiency (SFE) in the high-α sequence of ~4.5 × 10–10 yr–1, which is quite close to the nearly constant value found in molecular-gas-dominated regions of nearby spirals. This result suggests that the early evolution of the Milky Way disk was characterized by stars that shared a similar star-formation history and were formed in a well-mixed, turbulent, and molecular-dominated ISM with a gas consumption timescale (SFE–1) of ~2 Gyr. Finally, while the two α-element sequences in the inner Galaxy can be explained by a single chemical evolutionary track, this cannot hold in the outer Galaxy, requiring, instead, a mix of two or more populations with distinct enrichment histories.