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 alpha-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 [alpha/Fe] vs. [Fe/H] distribution of this sample exhibits a bimodality in [alpha/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 alpha-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 [alpha/Fe] trend of the high-alpha 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-alpha sequence of ~4.5E-10 1/yr, 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 (1/SFE) of ~2 Gyr. Finally, while the two alpha-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.