Conditional probabilities with Dirac observables and the problem of time in quantum gravity

We combine the ``evolving constants'' approach to the construction of observables in canonical quantum gravity with the Page-Wootters formulation of quantum mechanics with a relational time for generally covariant systems. This overcomes the objections levied by Kucha\ifmmode \check{r}\else \v{r}\fi{} against the latter formalism. The construction is formulated entirely in terms of Dirac observables, avoiding in all cases the physical observation of quantities that do not belong in the physical Hilbert space. We work out explicitly the example of the parametrized particle, including the calculation of the propagator. The resulting theory also predicts a fundamental mechanism of decoherence.