Over the course of the past few decades, it has become clear that the class of metal-poor stars known as carbon-enhanced metal-poor (CEMP) stars are powerful probes of a number of areas of interest to contemporary astrophysics. I review the multiple lines of evidence that demonstrate the association of CEMP-no stars (which do not exhibit neutron-capture element enhancements) with the nucleosynthesis products of the very first stars, their likely birth place in low-mass mini-halos, and (once accreted by the halo) their role as tracers of the outer-halo population of the Galaxy. The CEMP-s stars (which exhibit enhancements of the heavy s-process elements), by contrast, are likely to have been born in more massive mini-halos, and serve as tracers of the inner-halo population. The well-known increasing frequency of CEMP-no stars (and newly recognized relative constancy of CEMP-s stars) with declining metallicity, and the identification of the primary groups in the Yoon-Beers diagram of A(C) vs. [Fe/H], provide the means to explore these associations in more detail, and to constrain numerical models of the formation of the Milky Way.