Bill and Willie have (of course) given correct answers in terms of the holonomy of the given torsion-free connection $\nabla$ on the $n$-manifold $M$. However, it should be pointed out that, practically, it is almost impossible to compute the holonomy of $\nabla$ directly, since this would require integrating the ODE that define parallel transport with respect to $\nabla$. Even though they are linear ODE, for most connections given explicitly by some functions $\Gamma^i_{jk}$ on a domain, one cannot perform their integration.

Although, as Bill pointed out, you cannot always tell from local considerations whether $\nabla$ is a metric connection, you can still get a lot of information locally, and this usually suffices to determine the only possibilities for $g$. The practical tests (carried out essentially by differentiation alone) were of great interest to the early differential geometers, but they don't get much mention in the modern literature.

For example, one should start by computing the curvature $R$ of $\nabla$, which is a section of the bundle $T\otimes T^\ast\otimes \Lambda^2(T^\ast)$. (To save typing, I won't write the $M$ for the manifold.)

Taking the trace (i.e., contraction) on the first two factors, one gets the $2$-form $tr(R)$. This must vanish identically, or else there cannot be any solutions of $\nabla g = 0$ for which $g$ is nondegenerate. (Geometrically, $\nabla$ induces a connection on $\Lambda^n(T^\ast)$ (i.e., the volume forms on $M$) and $tr(R)$ is the curvature of this connection. If this connection is not flat, then $\nabla$ doesn't have any parallel volume forms, even locally, and hence cannot have any parallel metrics.)

To get more stringent conditions, one should treat $g$ as an unknown section of the bundle $S^2(T^\ast)$, pair it with $R$ (i.e., 'lower an index') and symmetrize in the first two factors, giving a bilinear pairing $\langle g, R\rangle$ that is a section of $S^2(T^\ast)\otimes \Lambda^2(T^\ast)$. By the Bianchi identities, the equation $\langle g, R\rangle = 0$ must be satisfied by any solution of $\nabla g = 0$. Notice that these are linear equations on the coefficients of $g$. For most $\nabla$ when $n>2$, this is a highly overdetermined system that has no nonzero solutions and you are done. Even when $n=2$, this is usually $3$ independent equations for $3$ unknowns, and there is no non-zero solution.

Often, though, the equations $\langle g, R\rangle = 0$ define a subbundle (at least on a dense open set) of $S^2(T^\ast)$ of which all the solutions of $\nabla g= 0$ must be sections. (As long as $R$ is nonzero, this is a proper subbundle. Of course, when $R=0$, the connection is flat, and the sheaf of solutions of $\nabla g = 0$ has stalks of dimension $n(n{+}1)/2$.) The equations $\nabla g = 0$ for $g$ a section of this subbundle are then overdetermined, and one can proceed to differentiate them and derive further conditions. In practice, when there is a $\nabla$-compatible metric at all, this process spins down rather rapidly to a line bundle of which $g$ must be a section, and one can then compute the only possible $g$ explicitly if one can take a primitive of a closed $1$-form.

For example, take the case $n=2$, and assume that $tr(R)\equiv0$ but that $R$ is nonvanishing on some simply-connected open set $U\subset M$. In this case, the equations $\langle g, R\rangle = 0$ have constant rank $2$ over $U$ and hence define a line bundle $L\subset S^*(T^\ast U)$. If $L$ doesn't lie in the cone of definite quadratic forms, then there is no $\nabla$-compatible metric on $U$. Suppose, though, that $L$ has a positive definite section $g_0$ on $U$. Then there will be a positive function $f$ on $U$, unique up to constant multiples, so that the volume form of $g = f\ g_0$ is $\nabla$-parallel. (And $f$ can be found by solving an equation of the form $d(\log f) = \phi$, where $\phi$ is a closed $1$-form on $U$ computable explicitly from $\nabla$ and $g_0$. This is the only integration required, and even this integration can be avoided if all you want to do is test whether $g$ exists, rather than finding it explicitly.) If this $g$ doesn't satisfy $\nabla g = 0$, then there is no $\nabla$-compatible metric. If it does, you are done (at least on $U$).

The complications that Bill alludes to come from the cases in which the equations $\langle g, R\rangle = 0$ and/or their higher order consequences (such as $\langle g, \nabla R\rangle = 0$, etc.) don't have constant rank or you have some nontrivial $\pi_1$, so that the sheaf of solutions to $\nabla g = 0$ is either badly behaved locally or doesn't have global sections. Of course, those are important, but, as a practical matter, when you are faced with determining whether a given $\nabla$ is a metric connection, they don't usually arise.

2more comments