We present results from the Weather on Other Worlds Spitzer Exploration Science program to investigate photometric variability in L and T dwarfs, usually attributed to patchy clouds. We surveyed 44 L3-T8 dwarfs, spanning a range of $J-K_s$ colors and surface gravities. We find that 14/23 (61%; 95% confidence interval: 41%-78%) of our single L3-L9.5 dwarfs are variable with peak-to-peak amplitudes between 0.2% and 1.5%, and 5/16 (31%; 95% confidence interval: 14%-56%) of our single T0-T8 dwarfs are variable with amplitudes between 0.8% and 4.6%. After correcting for sensitivity, we find that 80% (95% confidence interval: 53%-100%) of L dwarfs vary by >0.2%, and 36% (95% confidence interval: 19%-52%) of T dwarfs vary by >0.4%. Given viewing geometry considerations, we conclude that photospheric heterogeneities causing >0.2% 3-5-micron flux variations are present on virtually all L dwarfs, and probably on most T dwarfs. A third of L dwarf variables show irregular light curves, indicating that L dwarfs may have multiple spots that evolve over a single rotation. Also, approximately a third of the periodicities are on time scales >10 h, suggesting that slowly-rotating brown dwarfs may be common. We observe an increase in the maximum amplitudes over the entire spectral type range, revealing a potential for greater temperature contrasts in T dwarfs than in L dwarfs. We find a tentative association (92% confidence) between low surface gravity and high-amplitude variability among L3-L5.5 dwarfs. Although we can not confirm whether lower gravity is also correlated with a higher incidence of variables, the result is promising for the characterization of directly imaged young extrasolar planets through variability.