We report the discovery of 34 stars in the Hamburg/ESO Survey (HES) for metal-poor stars and the Sloan Digital Sky Survey (SDSS) that have [Fe/H]<~-3.0. Their median and minimum abundances are [Fe/H]=-3.1 and -4.1, respectively, while 10 stars have [Fe/H]<-3.5. High-resolution, high signal-to-noise spectroscopic data --equivalent widths and radial velocities-- are presented for these stars, together with an additional four objects previously reported or currently being investigated elsewhere. We have determined the atmospheric parameters, effective temperature (T_eff_), and surface gravity (logg), which are critical in the determination of the chemical abundances and the evolutionary status of these stars. Three techniques were used to derive these parameters. Spectrophotometric fits to model atmosphere fluxes were used to derive T_eff_, logg, and an estimate of E(B-V); H{alpha}, H{beta}, and H{gamma} profile fitting to model atmosphere results provided the second determination of T_eff_and logg; and finally, we used an empirical T_eff_-calibrated H{delta} index, for the third, independent T_eff_determination. The three values of T_eff_ are in good agreement, although the profile fitting may yield systematically cooler T_eff_values, by ~100K. This collective data set will be analyzed in future papers in the present series to utilize the most metal-poor stars as probes of conditions in the early universe.