Volume of a geodesic ball

A Google search for the title of the question finds this article where the first five coefficients in the series expansion of the volume (in powers of $r$) are computed. The first term is the same as the Euclidean volume (proportional to $r^n$, in other words); then come higher-order corrections depending on the curvature.

It's simple, all right. As I realized not long after posting (and as Hans also suggested), the key is the exponential map. The tangent space $T_x M$ gets an inner product space structure from the Riemannian metric; we can isometrically identify it with $\mathbb{R}^n$. Now $\exp_x : \mathbb{R}^n \to M$ is a diffeomorphism on some small ball $B_{\mathbb{R}^n}(0,\epsilon)$; on this ball, straight lines map to length-minimizing geodesics (see Do Carmo, Riemannian Geometry, Proposition 3.6), and thus Euclidean balls map to geodesic balls of the same radius. Taking $\epsilon$ smaller if necessary, we can assume the Jacobian of $\exp_x$ is bounded away from $0$ and $\infty$ on $B_{\mathbb{R}^n}(0, \epsilon)$; thus for $r < \epsilon$ we have that $\operatorname{Vol}(B(x,r))$ is comparable to $\operatorname{Vol}(B_{\mathbb{R}^n}(0,r)) \sim r^n$.