In this paper, we consider a Riemannian manifold $M$ and the Poisson-Voronoi tessellation generated by the union of a fixed point $x_0$ and a Poisson point process of intensity $lambda$ on $M$. We obtain asymptotic expansions up to the second order for the means of several characteristics of the Voronoi cell associated with $x_0$, including its volume and number of vertices. In each case, the first term of the estimate is equal to the mean characteristic in the Euclidean setting while the second term may contain a particular curvature of $M$ at $x_0$: the scalar curvature in the case of the mean number of vertices, the Ricci curvature in the case of the density of vertices and the sectional curvatures in the cases of the volume and number of vertices of a section of the Voronoi cell. Several explicit formulas are also derived in the particular case of constant curvature. The key tool for proving these results is a new change of variables formula of Blaschke-Petkantschin type in the Riemannian setting. Finally, a probabilistic proof of the Gauss-Bonnet Theorem is deduced from the asymptotic estimate of the total number of vertices of the tessellation in dimension two.