The Euclidean metric in $\mathbb{R}^3$ induces a metric on a hyperboloid, and the shortest path will be shortest with respect to this distance. Standard coordinates on a hyperboloid $z^2 - x^2 - y^2 = 1$ would be
$$
x = \sinh(t) \sin \phi \qquad
y = \sinh(t) \cos \phi \qquad
z = \cosh(t)
$$
with the interval:
$$
\mathrm{d}s^2 = \cosh(2 t) \mathrm{d} t^2 + \sinh^2(t) \mathrm{d} \phi^2
$$
That means that non-zero Christoffel symbols are
$$
\Gamma^t_{tt}=\tanh(2t) \qquad \Gamma^t_{tt}=-\frac{1}{2}\tanh(2t) \qquad
\Gamma^\phi_{t\phi} = \Gamma^\phi_{\phi t} = \frac{1}{\tanh(t)}
$$
Geodesic equations are readily obtained:
$$
t^{\prime\prime}(s) + \tanh(2 t(s)) \left( (t^\prime(s))^2 - \frac{1}{2} (\phi^\prime(s))^2 \right) = 0 \qquad
\phi^{\prime\prime}(s) + \frac{2}{\tanh(t(s))} t^\prime(s) \phi^\prime(s) = 0
$$
It is not hard to see, that the latter equation admits an integral of motion, i.e. $\phi^\prime(s) \sinh^2(t(s)) = \mathcal{L}$, because
$$
\frac{\mathrm{d}}{\mathrm{d} s} \left( \phi^\prime(s) \sinh^2(t(s)) \right) = \sinh^2(t(s)) \left( \phi^{\prime\prime}(s) + \frac{2}{\tanh(t(s))} t^\prime(s) \phi^\prime(s) \right) \left. = \right|_{\text{eq. of motion}} = 0
$$
Unfortunately this does not get us any closer to the geometric interpretation of the geodesic. Is it an interesection of the hyperboloid with a plane containing two points ? I suspect so, but I do not see how to prove it.