In this article, we present the theoretical basis for an approach to Stein's method for probability distributions on Riemannian manifolds. Using a semigroup representation for the solution to the Stein equation, we use tools from stochastic calculus to estimate the derivatives of the solution, yielding a bound on the Wasserstein distance. We first assume the Bakry-Emery-Ricci tensor is bounded below by a positive constant, after which we deal separately with the case of uniform approximation on a compact manifold. Applications of these results are currently under development and will appear in a subsequent article.