Massive galaxy-scale outflows of gas are one of the most commonly invoked mechanisms to regulate the growth and evolution of galaxies throughout the universe. While the gas in outflows spans a large range of temperatures and densities, the cold molecular phase is of particular interest because molecular outflows may be capable of suppressing star formation in galaxies by removing the star-forming gas. We have conducted the first survey of molecular outflows at z > 4, targeting 11 strongly lensed dusty, star-forming galaxies (DSFGs) with high-resolution Atacama Large Millimeter/submillimeter Array observations of OH 119 mu m absorption as an outflow tracer. In this first paper, we give an overview of the survey, focusing on the detection rate and structure of molecular outflows. We find unambiguous evidence for outflows in 8/11 galaxies (73%), more than tripling the number known at z > 4. This implies that molecular winds in z > 4 DSFGs must have both a near-unity occurrence rate and large opening angles to be detectable in absorption. Lensing reconstructions reveal that 500 pc scale clumpy structures in the outflows are common. The individual clumps are not directly resolved, but from optical depth arguments we expect that future observations will require 50-200 pc spatial resolution to resolve them. We do not detect high-velocity [C ii] wings in any of the sources with clear OH outflows, indicating that [C ii] is not a reliable tracer of molecular outflows. Our results represent a first step toward characterizing molecular outflows at z > 4 at the population level, demonstrating that large-scale outflows are ubiquitous among early massive, dusty galaxies.