  Linear cosmological perturbation theory is pivotal to a theoretical
understanding of current cosmological experimental data provided e.g. by cosmic
microwave anisotropy probes. A key issue in that theory is to extract the gauge
invariant degrees of freedom which allow unambiguous comparison between theory
and experiment. When one goes beyond first (linear) order, the task of writing
the Einstein equations expanded to n'th order in terms of quantities that are
gauge invariant up to terms of higher orders becomes highly non-trivial and
cumbersome. This fact has prevented progress for instance on the issue of the
stability of linear perturbation theory and is a subject of current debate in
the literature. In this series of papers we circumvent these difficulties by
passing to a manifestly gauge invariant framework. In other words, we only
perturb gauge invariant, i.e. measurable quantities, rather than gauge variant
ones. Thus, gauge invariance is preserved non perturbatively while we construct
the perturbation theory for the equations of motion for the gauge invariant
observables to all orders. In this first paper we develop the general framework
which is based on a seminal paper due to Brown and Kuchar as well as the
realtional formalism due to Rovelli. In the second, companion, paper we apply
our general theory to FRW cosmologies and derive the deviations from the
standard treatment in linear order. As it turns out, these deviations are
negligible in the late universe, thus our theory is in agreement with the
standard treatment. However, the real strength of our formalism is that it
admits a straightforward and unambiguous, gauge invariant generalisation to
higher orders. This will also allow us to settle the stability issue in a
future publication.
