Chemical compositions are determined based on high-resolution spectroscopy for 137 candidate extremely metal-poor (EMP) stars selected from the Sloan Digital Sky Survey (SDSS) and its first stellar extension, the Sloan Extension for Galactic Understanding and Exploration (SEGUE). High-resolution spectra with moderate signal-to-noise (S/N) ratios were obtained with the High Dispersion Spectrograph of the Subaru Telescope. Most of the sample (approximately 80%) are main-sequence turnoff stars, including dwarfs and subgiants. Four cool main-sequence stars, the most metal-deficient such stars known, are included in the remaining sample. Good agreement is found between effective temperatures estimated by the SEGUE stellar parameter pipeline, based on the SDSS/SEGUE medium-resolution spectra, and those estimated from the broadband (V - K) 0 and (g - r)0 colors. Our abundance measurements reveal that 70 stars in our sample have [Fe/H] < -3, adding a significant number of EMP stars to the currently known sample. Our analyses determine the abundances of eight elements (C, Na, Mg, Ca, Ti, Cr, Sr, and Ba) in addition to Fe. The fraction of carbon-enhanced metal-poor stars ([C/Fe] > +0.7) among the 25 giants in our sample is as high as 36%, while only a lower limit on the fraction (9%) is estimated for turnoff stars. This paper is the first of a series of papers based on these observational results. The following papers in this series will discuss the higher-resolution and higher-S/N observations of a subset of this sample, the metallicity distribution function, binarity, and correlations between the chemical composition and kinematics of extremely metal-poor stars.