Over the past half century, astronomers have identified on the order of 2000 Very Metal Poor (VMP) stars with [Fe/H] < -2.0, and a few hundred Extremely Metal Poor (EMP) stars with [Fe/H] < -3.0, primarily from two large objective prism surveys, the HK survey of Beers and collaborators and the Hamburg/ESO Survey of Christlieb and colleagues. High-resolution spectroscopic follow-up of a subset of these stars has resulted in the discovery of interesting, but rare, individual stars that display characteristic elemental abundance patterns that are constraining models of the nature of first-generation stars, the initial mass function at low metallicity, the yields of early supernovae, and the operation and astrophysical sites(s) of the r-process and s-process. Application of a newly developed spectroscopic pipeline for SEGUE has already revealed the presence of at least 2500 VMP stars and several hundred EMP stars in the public SDSS archive (through DR-4). The color selection algorithm that is being used for SEGUE is discussed, and the efficiency of the identification of VMP stars in SEGUE is presented. Based on the early SEGUE test data, we estimate that some 20,000 VMP stars will be identified by this survey within the next three years. We also discuss current plans for the calibration and refinement of the SEGUE spectroscopic pipeline and for obtaining rapid high-resolution follow-up of the most interesting stars. T.C.B., S.T., and Y.L. acknowledge partial support from grant AST 04-06784, as well as from grant PHY 02-16783, Physics Frontier Center/Joint Institute for Nuclear Astrophysics (JINA), awarded by the US National Science Foundation. H.J.N acknowledges partial support from NSF grant AST 03-07571. J.E.N. acknowledges partial support from Australian Research Council Grant DP0342613.