Can one recover a metric from geodesics?

The short answer is no, the geodesics do not determine the metric. For example, in the Cayley-Klein model of hyperbolic geometry the geodesics are straight lines. It is however rather rare for two Riemannian metrics to have the same geodesics. In two dimensions these metrics were studied by Liouville (see Livre VI of Darboux's Théorie générale des surfaces). Their geodesic flow is completely integrable and, in fact, admits an additional integral of motion quadratic in the momenta.

A basic results is that if locally the geodesics are straight lines (or can be mapped to straight lines), the metric has constant curvature (Beltrami's theorem). Other rigidity results of this kind exist.

For more on this topic you can consult the works of Topalov and Matveev.

A simple counterexample is the space $\mathbb R^n$, with a metric $g_{ab}$ independent on the point. As examples, the Euclidean space $\mathbb R^n$, but also the Minkowski spacetime (which is semi-Riemannian, but has the same geodesics as $\mathbb R^4$). The geodesics are the lines in $\mathbb R^n$, no matter how we choose the constant metric $g_{ab}$. Hence, different metrics can give the same set of geodesics.

I hope that my ``answer'' will not be understood solely as a propaganda of my survey http://arxiv.org/abs/1101.2069 where I discussed

(1) how, given geodesics, to reconstruct a connection (in both cases: when geodesics are parameterised and not parameterised)

(2) how, given a class od projectively related connections, to reconstruct a metric, and what are advantages of additional curvature assumptions on the metric

(3) what is the freedom in reconstructing the metric by geodesics -- in particular I proved the statement wellknown to experts and mentionen by Robert Bryant in his comment that for generic metric the geodesics, even unparameterized, determine the metric.