We present an analysis of the substructure revealed by RR Lyraes in Sloan Digital Sky Survey Stripe 82, which covers in declination on the celestial equator over the right ascension range to. We use the new public archive of light-motion curves in Stripe 82, published by Bramich et al. in 2008, to identify a set of high-quality RR Lyrae candidates. Period estimates are determined to high accuracy using a string-length method. A subset of 178 RR Lyraes with spectrally derived metallicities are employed to derive metallicity-period-amplitude relations, which are then used, together with archive magnitude data and light-curve Fourier decomposition, to estimate metallicities and hence distances for the entire sample. The RR Lyraes lie 5-115 kpc from the Galactic Centre, with distance estimates accurate to ∼8 per cent. The RR Lyraes are further divided into subsets of 316 RRab types and 91 RRc types based on their period, colour and metallicity. We fit a smooth density law to the distribution as a simple representation of the data. For Galactocentric radii 5-25 kpc the number density of RR Lyraes falls as r -2.4, but beyond 25 kpc, the number density falls much more steeply, as r-4.5. However, we stress that in practice the density distribution is not smooth, but dominated by clumps and substructure. Samples of 55 and 237 RR Lyraes associated with the Sagittarius Stream and the Hercules-Aquila Cloud, respectively, are identified. Hence, ∼70 per cent of the RR Lyraes in Stripe 82 belong to known substructure, and the sharp break in the density law reflects the fact that the dominant substructure in Stripe 82 - the Hercules-Aquila Cloud and the Sagittarius Stream - lie within 40 kpc. In fact, almost 60 per cent of all the RR Lyraes in Stripe 82 are associated with the Hercules-Aquila Cloud alone, which emphasizes the cloud's pre-eminence. Additionally, evidence of a new and distant substructure - the Pisces Overdensity - is found, consisting of 28 faint RR Lyraes centred on Galactic coordinates (ℓ ≈ 80°, b ≈ -55°), with distances of ∼80 kpc. The total stellar mass in the Pisces Overdensity is ∼104 M⊙ and its metallicity is [Fe/H] ∼ -1.5.