We report on spectroscopic observations for 1044 stars, located primarily in the southern Galactic hemisphere, chosen from a list of candidate metal-deficient stars discovered in the HK objective-prism survey. Metal abundances for the program stars, on the [Fe/H] scale, are obtained from a previously published calibration of the variation in the equivalent width of the Ca II K absorption line (lambda-3933 angstrom) as a function of broadband (B-V)0 color. Broadband UBV photometry is available for roughly one-third of the present sample. For the majority of stars without available photometry (primarily stars with an inferred [Fe/H] > -2.0), we obtain estimated dereddened (B-V)0 colors from an empirical calibration of the variation of Balmer line equivalent width with broadband color. Radial velocities, with accuracies on the order of 10 km s-1, are obtained for all our program stars. Distance estimates, accurate to 10%-15%, are reported for the subsample of program stars with available photometry. Less accurate distances are obtained for the remaining stars by a calibration of apparent magnitude with crude brightness estimates from the original survey plates. The sample reported here includes 734 stars with [Fe/H] less-than-or-equal-to -1.0, 446 stars with [Fe/H] less-than-or-equal-to -2.0, 70 stars with [Fe/H] less-than-or-equal-to -3.0, and at least three stars with [Fe/H] less-than-or-equal-to -4.0. Due to uncertainties in the calibration of our metal-abundance determinations for late-type stars, the actual number of stars with [Fe/H] less-than-or-equal-to -4.0 in the present sample may be on the order of 5-10. Fifty stars in our sample exhibit anomalously strong G bands, characteristic of the subgiant CH stars discussed by Bond. Among the most metal-deficient objects (as inferred from their Ca II K equivalent widths), we identify six stars with moderate to strong CN bands. The present program stars form the basis for addressing a wide range of questions concerning the formation and evolution of the Galactic halo population, and, by inference, the nature of the first generations of star formation in the universe. The number of extremely metal-poor stars ([Fe/H] less-than-or-equal-to -2.0) reported in the present sample is roughly quadruple the sample size of nonkinematically selected stars of similar metal abundance reported by previous workers, and is on the order of the total previous samples of stars in this abundance regime when all sources are included. The number of stars with [Fe/H] less-than-or-equal-to -3.0 in the present sample is seven times the number of previously identified stars with spectroscopically determined abundances which are this low. We emphasize, however, that the present sample only represents on the order of 10% of the number of such extreme objects that remain to be discovered upon completion of the follow-up spectroscopy and photometry of metal-deficient candidates identified in our ongoing objective-prism survey.