We show how staggered fermions can be coupled to gravity by generalizing them to Kaehler-Dirac fermions. The latter experience a perturbative gravitational anomaly which breaks
a U(1) symmetry down to Z_4. This anomaly is captured exactly by the lattice theory. Furthermore we show that this theory exhibits a second
non-perturbative 't Hooft anomaly which can be seen
by considering propagation on non-orientable spaces. This anomaly can be
cancelled for multiples of two Kaehler-Dirac fields. This observation explains recent work that shows that multiples of two staggered fermions can be gapped without breaking symmetries.