An understanding of the interaction between ceria and environmentally sensitive molecules is vital for developing its role in catalysis. We present the structure and energetics of CO adsorbed onto stoichiometric (111), (110), and (100) surfaces of ceria from first principles density functional theory corrected for on-site Coulomb interactions, DFT+U. DFT+U is applied because it can describe consistently the properties of both the stoichiometric and reduced surfaces. Our major finding is that the interaction is strongly surface dependent, consistent with experiment. Upon interaction of CO with the (111) surface, weak binding is found, with little perturbation to the surface or the molecule. For the (110) and (100) surfaces, the most stable adsorbate is that in which the CO molecule bridges two oxygen atoms and pulls these atoms out of their lattice sites, with formation of a (CO3) species. This results in a strong modification to the surface structure, consistent with that resulting from mild reduction. The electronic structure also demonstrates reduction of the ceria surface and consequent localization of charge on cerium atoms neighboring the vacancy sites. The surface-bound (CO3) species is identified as a carbonate, (CO3)(2-)group, which is formed along with two reduced surface Ce(III) ions, in good agreement with experimental infrared data. These results provide a detailed investigation of the interactions involved in the adsorption of CO on ceria surfaces, allowing a rationalization of experimental findings and demonstrate further the applicability of the DFT+U approach to the study of systems in which reduced ceria surfaces play a role.