We explore the cosmological halo-to-halo scatter of the distribution of mass within dark matter halos utilizing a well-resolved statistical sample of clusters from the cosmological Millennium simulation. We find that at any radius, the spherically-averaged dark matter density of a halo (corresponding to the smooth-component) and its logarithmic slope are well-described by a Gaussian probability distribution. At small radii (within the scale radius), the density distribution is fully determined by the measured Gaussian distribution in halo concentrations. The variance in the radial distribution of mass in dark matter halos is important for the interpretation of direct and indirect dark matter detection efforts. The scatter in mass profiles imparts approximately a 25 percent cosmological uncertainty in the dark matter density at the Solar neighborhood and a factor of ~3 uncertainty in the expected Galactic dark matter annihilation flux. The aggregate effect of halo-to-halo profile scatter leads to a small (few percent) enhancement in dark matter annihilation background if the Gaussian concentration distribution holds for all halo masses versus a 10 percent enhancement under the assumption of a log-normal concentration distribution. The Gaussian nature of the cluster profile scatter implies that the technique of stacking halos to improve signal to noise should not suffer from bias.