Dark matter halos host galaxies, but cold dark matter is expected to cluster on much smaller scales as well. Small-scale dark matter structures would host no visible matter but can still leave hints about the nature of dark matter. If the dark matter is a thermal relic, the smallest structures are rho ~ r^-1.5 density cusps that arose at the onset of structure formation in the universe. For WIMP models, these cusps may be Earth-mass, and their great abundance and high internal density lead them to dominate the annihilation rate at the present time. Gravitational signatures of small-scale dark structures are more difficult to access, but gravitational detection is possible for minihalos arising in scenarios with amplified small-scale density perturbations.