Recently, we proposed paleo-detectors as a method for the direct detection of
Weakly Interacting Massive Particle (WIMP) dark matter. In paleo-detectors, one
would search for the persistent traces left by dark matter-nucleon interactions
in ancient minerals. Thanks to the large integration time of paleo-detectors,
relatively small target masses suffice to obtain exposures, i.e. the product of
integration time and target mass, much larger than what is feasible in the
conventional direct detection approach. Here, we discuss the paleo-detector
proposal in detail, in particular, a range of background sources. For low-mass
WIMPs with masses $m_\chi\lesssim10\,$GeV, the largest contribution to the
background budget comes from nuclear recoils induced by coherent scattering of
solar neutrinos. For heavier WIMPs, the largest background source is nuclear
recoils induced by fast neutrons created by heavy radioactive contaminants,
particularly $^{238}$U; neutrons can arise in spontaneous fission or from
$\alpha$-particles created in $^{238}$U decays. We also discuss the challenges
of mineral optimization, specifically the determination of readily available
minerals from rocks in deep boreholes which are able to record persistent
damage from nuclear recoils. In order to suppress backgrounds induced by
radioactive contaminants, we propose to use minerals found in marine evaporites
or in ultra-basic rocks. We estimate the sensitivity of paleo-detectors to
spin-independent and spin-dependent WIMP-nucleus interactions. In all
interaction cases considered here, the sensitivity to low-mass WIMPs with
masses $m_\chi\lesssim10\,$GeV extends to WIMP-nucleon cross sections many
orders of magnitude smaller than current upper limits. For heavier WIMPs with
masses $m_\chi\gtrsim30\,$GeV cross sections a factor of a few to $\sim100$
smaller than current upper limits can be probed by paleo-detectors. [Abridged]