There are several hundred thousand R = 2000 stellar spectra reported in the final public release of the Sloan Digital Sky Survey (SDSS-I) and the continuation project SEGUE (Sloan Extension for Galactic Exploration and Understanding), which has completed roughly half of its scheduled set of observations to date. The stars in this sample were targeted for a wide variety of reasons, and hence do not represent a sample from which an unbiased metallicity distribution function (MDF) of stars in the halo or thick-disk populations may be drawn. However, there exist over 9000 stars with estimated metallicities [Fe/H]>-2.0 and effective temperatures in the range 5000K < Teff < 7000K among this sample, based on application of the SDSS/SEGUE spectroscopic parameter analysis pipeline. We have continued to refine estimates of the stellar parameters for these stars, using an automated synthetic spectrum approach. This technique produces estimates of [Fe/H] as well as [C/Fe] (or upper limits on these quantitites) based on MOOG syntheses of the region of spectrum around the CaII K line and the CH G band, respectively. This sample represents, by a factor of more than three, the largest database of very metal-poor stars yet assembled. A least 1000 of these stars have g < 16.5, and hence are amenable to high-resolution spectroscopic studies with presently available large-aperture telescopes. We report on the catalog of these stars, and consider the shape of the low-metallicity tail of the halo MDF derived from these data. Funding for the SDSS and SDSS-II has been provided by the Alfred P. Sloan Foundation, the Participating Institutions, the National Science Foundation, the U.S. Department of Energy, the National Aeronautics and Space Administration, the Japanese Monbukagakusho, the Max Planck Society, and the Higher Education Funding Council for England. The SDSS Web Site is http://www.sdss.org/.