This work investigates the dark matters structures that form on the smallest cosmological scales. We find that the types and abundances of structures which form at approximately Earth-mass scales are very sensitive to the nature of dark matter. We explore various candidates for dark matter and determine the corresponding properties of small-scale structure. In particular, we discuss possibilities for indirect detection of dark matter through small-scale structure, and comment on the potential of these methods for discriminating between dark matter candidates.