We study spacetime diffeomorphisms in the Hamiltonian and Lagrangian formalisms of generally covariant systems. We show that the gauge group for such a system is characterized by having generators which are projectable under the Legendre map. The gauge group is found to be much larger than the original group of spacetime diffeomorphisms, since its generators must depend on the lapse function and shift vector of the spacetime metric in a given coordinate patch. Our results are generalizations of earlier results by Salisbury and Sundermeyer. They arise in a natural way from using the requirement of equivalence between Lagrangian and Hamiltonian formulations of the system, and they are new in that the symmetries are realized on the full set of phase space variables. The generators are displayed explicitly and are applied to the relativistic string and to general relativity.