We study the effects of substructure in the Galactic halo on direct detection of dark matter, on searches for energetic neutrinos from WIMP annihilation in the Sun and Earth, and on the enhancement in the WIMP annihilation rate in the halo. Our central result is a probability distribution function (PDF) P(\rho) for the local dark-matter density. This distribution must be taken into account when using null dark-matter searches to constrain the properties of dark-matter candidates. We take two approaches to calculating the PDF. The first is an analytic model that capitalizes on the scale-invariant nature of the structure--formation hierarchy in order to address early stages in the hierarchy (very small scales; high densities). Our second approach uses simulation-inspired results to describe the PDF that arises from lower-density larger-scale substructures which formed in more recent stages in the merger hierarchy. The distributions are skew positive, and they peak at densities lower than the mean density. The local dark-matter density may be as small as 1/10th the canonical value of ~ 0.4 GeV/cm^3, but it is probably no less than 0.2 GeV/cm^3.