The accuracy of outdoor sound propagation predictions is often limited by imperfect knowledge of the atmospheric and ground properties, and random environmental variations such as turbulence. This article describes the impact of such uncertainties, and how they can be efficiently addressed and quantified with stochastic sampling techniques such as Monte Carlo and Latin hypercube sampling (LHS). Extensions to these techniques, such as importance sampling based on simpler, more efficient propagation models, and adaptive importance sampling, are described. A relatively simple example problem involving the Lloyd's mirror effect for an elevated sound source in a homogeneous atmosphere is considered first, followed by a more complicated example involving near-ground sound propagation with refraction and scattering by turbulence. When uncertainties in the atmospheric and ground properties dominate, LHS with importance sampling is found to converge to an accurate estimate with the fewest samples. When random turbulent scattering dominates, the sampling method has little impact. A comprehensive computational approach is demonstrated that is both efficient and accurate, while simultaneously incorporating broadband sources, turbulent scattering, and uncertainty in the environmental properties.