We calculate the relic abundance of thermally produced neutralino cold dark matter in the general 19 parameter supergravity (SUGRA-19) model. A scan over GUT scale parameters reveals that models with a bino-like neutralino typically give rise to a dark matter density \Omega_{\tz_1}h^2\sim 1-1000, i.e. between 1 and 4 orders of magnitude higher than the measured value. Models with higgsino or wino cold dark matter can yield the correct relic density, but mainly for neutralino masses around 700-1300 GeV. Models with mixed bino-wino or bino-higgsino CDM, or models with dominant co-annihilation or A-resonance annihilation can yield the correct abundance, but such cases are extremely hard to generate using a general scan over GUT scale parameters; this is indicative of high fine-tuning of the relic abundance in these cases. Requiring that m_{\tz_1}\alt 500 GeV (as a rough naturalness requirement) gives rise to a minimal probably dip in parameter space at the measured CDM abundance. For comparison, we also scan over mSUGRA space with four free parameters. Finally, we investigate the Peccei-Quinn augmented MSSM with mixed axion/axino cold dark matter. In this case, the relic abundance agrees more naturally with the measured value. In light of our cumulative results, we conclude that future axion searches should probe much more broadly in axion mass, and deeper into the axion coupling.

Over almost all of minimal supergravity (mSUGRA or CMSSM) model parameter space, there is a large overabundance of neutralino cold dark matter (CDM). We find that the allowed regions of mSUGRA parameter space which match the measured abundance of CDM in the universe are highly fine-tuned. If instead we invoke the Peccei-Quinn-Weinberg-Wilczek solution to the strong CP problem, then the SUSY CDM may consist of an axion/axino admixture with an axino mass of order the MeV scale, and where mixed axion/axino or mainly axion CDM seems preferred. In this case, fine-tuning of the relic density is typically much lower, showing that axion/axino CDM (a\tilde{a}CDM) is to be preferred in the paradigm model for SUSY phenomenology. For mSUGRA with a\tilde{a}CDM, quite different regions of parameter space are now DM-favored as compared to the case of neutralino DM. Thus, rather different SUSY signatures are expected at the LHC in the case of mSUGRA with a\tilde{a}CDM, as compared to mSUGRA with neutralino CDM.

We examine the minimal supergravity (mSUGRA) model under the assumption that the strong CP problem is solved by the Peccei-Quinn mechanism. In this case, the relic dark matter (DM) abundance consists of three components: {\it i}). cold axions, {\it ii}). warm axinos from neutralino decay, and {\it iii}). cold or warm thermally produced axinos. To sustain a high enough re-heat temperature (T_R\agt 10^6 GeV) for many baryogenesis mechanisms to function, we find that the bulk of DM should consist of cold axions, while the admixture of cold and warm axinos should be rather slight, with a very light axino of mass \sim 100 keV. For mSUGRA with mainly axion cold DM (CDM), the most DM-preferred parameter space regions are precisely those which are least preferred in the case of neutralino DM. Thus, rather different SUSY signatures are expected at the LHC in the case of mSUGRA with mainly axion CDM, as compared to mSUGRA with neutralino CDM.