At the level of representation theory, the diffeomorphism group in general relativity and its extensions plays the very same role as Yang-Mills symmetries in gauge theories. In both cases, one may define the action of the symmetry on the operators.
In both cases, only the gauge-invariant states - singlets - are allowed in the physical spectrum. That's why the representation theory of the gauge group plays no role at the level of the Hilbert space - only the singlets are relevant. That's why the "gauge symmetries" always just reduce the number of independent degrees of freedom and many people prefer to call them "gauge redundancies" rather than "gauge symmetries".
In both cases, the latter condition of gauge invariance ("physical states are singlets") must totally hold for transformations that converge to the identity at infinity. In both cases, there are subtleties for transformations that change the asymptotic region (fields at spatial infinity). In both cases, the gauge invariance of the physical states arises as the quantum version of the Gauss's law - the subset of Maxwell's or Einstein's equations that don't contain any time derivatives and may therefore be considered constraints on the initial state rather than evolution equations: it's the $\mbox{div} D=\rho$ equation in the case of electromagnetism. The corresponding operator $(\mbox{div} D-\rho)$ has to annihilate the physical states $|\psi \rangle$ in the quantum theory (which is non-trivial if the quantum theory is formulated in terms of the redundant fields, the gauge potentials). A total analogy exists for Einstein's equations (extrinsic curvature on the slice enters the constraint).
The difference between the two gauge groups is just in the "details" - how they act on the spacetime.
The Yang-Mills transformations are local, so $\phi(x,y,z,t)$ only changes by other fields at the same point $(x,y,z,t)$: imagine a phase transformation of a charged field $\phi$, for example. In the case of diffeomorphism, the change is nonlocal: the field at one point depends on the fields at another point $(x',y',z',t')$ before the transformation.
This technical difference changes the character of gauge-invariant observables - and only gauge-invariant observables may correspond to numbers that make a physical sense and may be measured. Because the gauge transformations in the gauge theory are local, one may construct gauge-invariant local operators such as $\mbox{Tr}(F_{\mu\nu} (x,y,z,t)F^{\mu\nu}(x,y,z,t))$, to choose a random example.
In the case of general relativity, such quantities are not gauge-invariant because e.g. the Ricci scalar $R(x,y,z,t)$ is transformed to the Ricci scalar at another point $R(x',y',z',t')$, so even the Ricci scalar at a given point is not gauge-invariant. To construct gauge-invariant observables in general relativity, one has to be sensitive to - e.g. integrate over - the whole space (or spacetime). For example, the ADM energy is gauge-invariant in asymptotically flat backgrounds.
A physical apparatus that exists in a gravitational theory is not represented by any local observable - in the technical sense of "local" - because its location is not a gauge-invariant quantity. If you have a small device in the vicinity of $(x,y,z,t)=(0,0,0,0)$, its measured results may be expressed as a functional of the fields in the vicinity of $(0,0,0,0)$. However, that's only true in one coordinate system. In other words, it is only true before you make a general gauge transformation. After the gauge transformation, the form of the observable corresponding to the quantity measured by the apparatus is expressed by a different formula involving the physical fields - the new formula depends on fields at different values of $(x,y,z,t)$.
You may "know" that $(0,0,0,0)$ is "physically" the same point as $(7,2,-3,5)$ in some new coordinates but the mathematics doesn't know it: the form of the expression is changed so the quantity is not gauge-invariant. In the same way, you could claim that you know that a "red quark field" before the $SU(3)$ transformation is "physically" the same thing as a "green quark field" after the transformation - because you also know the transformation. But exactly because the form of the field that corresponds to the "same physical thing" depends on the transformation, we say that colorful fields in QCD - and local operators in GR - are not gauge-invariant.
You may pinpoint the location of the gadget by defining its proper distances from $d-1=3$ points A,B,C at "infinity" or "far enough" where you already require the legitimate gauge transformations (coordinate redefinitions) to be trivial. But the calculation of the point - and the fields at this point - will depend on the metric tensor between the apparatus and the points A,B,C. So the definition of the observables that represent the values measured by the apparatus is manifestly and inevitably non-local.
Again, there are no gauge-invariant observables in a theory with a coordinate reparametrization symmetry. I claim that the text above makes it totally clear but if it is not clear, please write down something that you think is a gauge-invariant local quantity - as a function of the basic degrees of freedom - in a theory with the general covariance and I will show you why it is not a gauge-invariant local quantity. There aren't any.
I will mostly talk about the classical physics as this is complicated enough already (I might mention something about quantum stuff at the end). So, let us first get all the relevant terms straight, so that we avoid any further confusion. In particular, we need to be precise about what we mean by invariance because already two different notions have been thrown into one bag.
A symmetry group of a physical system is a group of transformations that leave the system invariant. E.g. the electric field of a point charge is invariant under rotations w.r.t. to that point. In other words, we want the group to act trivially. But that means that this immediatelly rules out any equations that carries tensorial indices (i.e. transforms in a non-trivial representation of the rotation group). For these equations, if you perform a rotation, the equation will change. Of course, it will change in an easily describable manner and a different observer will agree. But the difference is crucial. E.g. in classsical quantum mechanics we require the equations to be scalar always (which is reflected in the fact that Hamiltonian transforms trivially under the symmetry group).
Carrying a group action is a broader term that includes tensorial equations we have left out in the previous bullet point. We only require that equations or states are being acted upon by a group. Note that the group action need not have any relation to the symmetry. E.g. take the point charge and translate it. This will certainly produce a different system (at least if there is some background so that we can actually distinguish points).
A gauge group of a system is a set of transformations that leave the states invariant. What this means is that the actual states of the system are equivalence classes of orbits of the gauge group. Explicitly, consider the equation ${{\rm d} \over {\rm d} x} f(x) = 0$. This has a solution $g(x) \equiv C$ for any $C$. But if we posit that the gauge group of the equation consists of the transformations $f(x) \mapsto f(x) + a$ then we identify all the constant solutions and are left with a single equivalence class of them -- this will be the physical state. This is what gauge groups do in general: they allow us to treat equivalence classes in terms of their constituents. Obviously, gauge groups are completely redundant. The reason people work with gauge groups in the first place is that the description of the system may simplify after introduction of these additional parameters that "see" into the equivalence class. Of course historical process went backwards: since gauge-theoretical formulation is simpler, this is whan people discovered first and they only noticed the presence of the gauge groups afterwards.
Now, having said this, let's look at the electromagnetism (first in the flat space). What symmetries are the Maxwell equations invariant under? One would like to say under Lorentz group but this actually not the case. Let's look at this more closely. As alluded to previously the equation
$$\partial_{\mu} F^{\mu \nu} = J^{\nu}$$
can't really be invariant since it carries a vector index. It transforms in the four-vector representation of the Lorentz group, yes -- but it is certainly not invariant. Contrast this with the Minkowski space-time itself which is left invariant by the Lorentz group.
We also have ${\rm d} F = 0$ and therefore (in a contractible space-time) also $F = {\rm d} A$ which is obviously invariant w.r.t. to $A \mapsto A + {\rm d} \chi$. In terms of the above discussion the equivalence class $A + {\rm d} \Omega^0({\mathbb R}^{1,3})$ is the physical state and the gauge transformation lets us distinguish between its constituents
Let's move to a curved spacetime now. Then we have
$$\nabla_{\mu} F^{\mu \nu} = J^{\nu}$$
Again, this is not invariant under ${\rm Diff}(M)$. But it transforms under an action of ${\rm Diff}(M)$. The only thing in sight that is invariant under ${\rm Diff}(M)$ is $M$ itself (by definition).
In the very same way, GR is not invariant under ${\rm Diff}(M)$ but only transforms under a certain action of it (different than EM though, since GR equations carry two indices). Also, ${\rm Diff}(M)$ can't possibly be a gauge group of any of these systems since it would imply that almost all possible field configurations get cramped to a single equivalence class possibly indexed by some topological invariant which can't be changed by a diffeomorphism. In other words, theory with ${\rm Diff}(M)$ as a gauge group would need to be purely topological with no local degrees of freedom.
Best Answer
Instead of re-inventing the wheel, here is a bunch of references:
Here is something I wrote back when I was blogging, the discussion was kind of fun.
There is also a pretty good explanation in this paper by Giddings- Hartle-Marolf on how this statement doesn't contradict all kind of semi-intuitive ideas people have (and started commenting on here already) about local observables.
Finally, this paper by Arkani-Hamed and collaborators has very nice introduction explaining why dynamical gravity, and not just Diff invariance, is what prevents the existence of local observables.