Carbon-enhanced metal-poor (CEMP) stars comprise almost a third of stars with [Fe/H]<-2, although their origins are still poorly understood. It is highly likely that one sub-class (CEMP-s stars) is tied to mass-transfer events in binary stars, while another sub-class (CEMP-no stars) are enriched by the nucleosynthetic yields of the first generations of stars. Previous studies of CEMP stars have primarily concentrated on the Galactic halo, but more recently they have also been detected in the thick disc and bulge components of the Milky Way. Gaia DR3 has provided an unprecedented sample of over 200 million low-resolution (R~50) spectra from the BP and RP photometers. Training on the CEMP catalogue from the SDSS/SEGUE database, we use XGBoost to identify the largest all-sky sample of CEMP candidate stars to date. In total, we find 58872 CEMP star candidates, with an estimated contamination rate of 12 per cent. When comparing to literature high-resolution catalogues, we positively identify 60-68 per cent of the CEMP stars in the data, validating our results and indicating a high completeness rate. Our final catalogue of CEMP candidates spans from the inner to outer Milky Way, with distances as close as r~0.8kpc from the Galactic centre, and as far as r>30kpc. Future higher resolution spectroscopic follow-up of these candidates will provide validations of their classification and enable investigations of the frequency of CEMP-s and CEMP-no stars throughout the Galaxy, to further constrain the nature of their progenitors.