We describe a new method to search for metal-poor candidates from the Hamburg/ESO objective-prism survey (HES) based on identifying stars with apparently strong CH G-band strengths for their colors. The hypothesis we exploit is that large overabundances of carbon are common among metal-poor stars, as has been found by numerous studies over the past two decades. The selection was made by considering two line indices in the 4300{AA} region, applied directly to the low-resolution prism spectra. This work also extends a previously published method by adding bright sources to the sample. The spectra of these stars suffer from saturation effects, compromising the index calculations and leading to an undersampling of the brighter candidates. A simple numerical procedure, based on available photometry, was developed to correct the line indices and overcome this limitation. Visual inspection and classification of the spectra from the HES plates yielded a list of 5288 new metal-poor (and by selection, carbon-rich) candidates, which are presently being used as targets for medium-resolution spectroscopic follow-up. Estimates of the stellar atmospheric parameters, as well as carbon abundances, are now available for 117 of the first candidates, based on follow-up medium-resolution spectra obtained with the SOAR 4.1m and Gemini 8m telescopes. There are eight newly discovered stars with [Fe/H] < -3.0 in our sample, including two with [Fe/H] < -3.5.