We consider in detail the problem of gauge dependence that exists in relativistic perturbation theory, going beyond the linear approximation and treating second-and higher-order perturbations. We first derive some mathematical results concerning the Taylor expansion of tensor fields under the action of one-parameter families (not necessarily groups) of diffeomorphisms. Secondly, we define gauge invariance to an arbitrary order n. Finally, we give a generating formula for the gauge transformation to an arbitrary order and explicit rules to second and third order. This formalism can be used in any field of applied general relativity, such as cosmological and black hole perturbations, as well as in other spacetime theories. As a specific example, we consider here second-order perturbations in cosmology, assuming a 7 flat Robertson-Walker background, giving explicit second-order transformations between the synchronous and the Poisson (generalized longitudinal) gauges.