A deformation of the algebra of diffeomorphisms is constructed for
canonically deformed spaces with constant deformation parameter theta. The
algebraic relations remain the same, whereas the comultiplication rule (Leibniz
rule) is different from the undeformed one. Based on this deformed algebra a
covariant tensor calculus is constructed and all the concepts like metric,
covariant derivatives, curvature and torsion can be defined on the deformed
space as well. The construction of these geometric quantities is presented in
detail. This leads to an action invariant under the deformed diffeomorphism
algebra and can be interpreted as a theta-deformed Einstein-Hilbert action. The
metric or the vierbein field will be the dynamical variable as they are in the
undeformed theory. The action and all relevant quantities are expanded up to
second order in theta.