A generalization of the Renormalization Group, which describes order-parameter fluctuations in finite systems, is developed in the specific context of percolation. This ``Stochastic Renormalization Group'' (SRG) expresses statistical self-similarity through a non-stationary branching process. The SRG provides a theoretical basis for analytical or numerical approximations, both at and away from criticality, whenever the correlation length is much larger than the lattice spacing (regardless of the system size). For example, the SRG predicts order-parameter distributions and finite-size scaling functions for the complete crossover between phases. For percolation, the simplest SRG describes structural quantities conditional on spanning, such as the total cluster mass or the minimum chemical distance between two boundaries. In these cases, the Central Limit Theorem (for independent random variables) holds at the stable, off-critical fixed points, while a ``Fractal Central Limit Theorem'' (describing long-range correlations) holds at the unstable, critical fixed point. This first part of a series of articles explains these basic concepts and a general theory of crossover. Subsequent parts will focus on limit theorems and comparisons of small-cell SRG approximations with simulation results.

33 pages, 6 figures, to appear in Physica A; v2: some typos corrected and Eqs. (26)-(27) cast in a simpler (but equivalent) form