We present the quantitative methods used for selecting candidate metal-poor stars in the Hamburg/ESO objective-prism survey (HES). The selection is based on the strength of the Ca II K line, B-V colors (both measured directly from the digital HES spectra), as well as J-K colors from the 2 Micron All Sky Survey. The KP index for Ca II K can be measured from the HES spectra with an accuracy of 1.0 Angstrom, and a calibration of the HES B-V colors, using CCD photometry, yields a 1-sigma uncertainty of 0.07 mag for stars in the color range 0.3 < B-V < 1.4. These accuracies make it possible to reliably reject stars with [Fe/H] > -2.0 without sacrificing completeness at the lowest metallicities. A test of the selection using 1121 stars of the HK survey of Beers, Preston, and Shectman present on HES plates suggests that the completeness at [Fe/H] < -3.5 is close to 100% and that, at the same time, the contamination of the candidate sample with false positives is low: 50% of all stars with [Fe/H] > -2.5 and 97% of all stars with [Fe/H] > -2.0 are rejected. The selection was applied to 379 HES fields, covering a nominal area of 8853 square degrees of the southern high Galactic latitude sky. The candidate sample consists of 20,271 stars in the magnitude range 10 < B < 18. A comparison of the magnitude distribution with that of the HK survey shows that the magnitude limit of the HES sample is about 2 mag fainter. Taking the overlap of the sky areas covered by both surveys into account, it follows that the survey volume for metal-poor stars has been increased by the HES by about a factor of 10 with respect to the HK survey. We have already identified several very rare objects with the HES, including, e.g., the three most heavy-element deficient stars currently known.