How can generic closed geodesics on surfaces of negative curvature be constructed? As far as I understand it the closing lemma implies that closed geodesics on surfaces of negative curvature are dense. So: how can they be constructed in general?
A concrete answer that dovetails with the construction of such surfaces with constant negative curvature and genus $g$ from regular hyperbolic $(8g-4)$-gons along lines indicated by Adler and Flatto and gives the endpoints of the geodesics in the Poincaré disk model would be ideal. More useful still would be a way to construct all the closed geodesics that cross the boundaries of translates of the fundamental $(8g-4)$-gon some specified number of times (I am pretty sure this ought to be a finite set, but I couldn't say why off the top of my head).
 A: If you think of your surface as the upper half plane modulo a group of Moebius transformations $G$, start by representing each of your Moebius transformations $ z \longmapsto \frac{az+b}{cz+d}$ by a Matrix.
$$A = \pmatrix{ a & b \\\ c & d}$$
And since only the representative in $PGL_2(\mathbb R)$ matters, people usually normalize to have $Det(A) = \pm 1$.
The standard classification of Moebius transformations as elliptic / parabolic / hyperbolic (loxodromic) is in terms of the determinant and trace squared.  You're hyperbolic if and only if the trace squared is larger than $4$.  Hyperbolic transformations are the ones with no fixed points in the interior of the Poincare disc, and two fixed points on the boundary, and they are rather explicitly "translation along a geodesic".  
Elliptic transformations fix a point in the interior of the disc so they can't be covering transformations.  Parabolics you only get as covering transformations if the surface is non-compact, because parabolics have one fixed point and its on the boundary -- if you had such a covering transformation it would tell you your surface has non-trivial closed curves such that the length functional has no lower bound in its homotopy class. 
So your covering tranformations are only hyperbolic.  That happens only when $tr(A)^2 > 4$.  So how do you find your axis?  It's the geodesic between the two fixed points on the boundary, so you're looking for solutions to the equation:
$$ t = \frac{at+b}{ct+d}$$
for $t$ real, this is a quadratic equation in the real variable $t$.  If I remember the quadratic equation those two points are:
$$ \frac{tr(A) \pm \sqrt{tr(A)^2 - 4Det(A)}}{2c}$$
Is this what you're after?  
A: Are you willing to buy that the set of  non-closed geodesics are dense?  If so, here is an argument that goes back to Birkhoff and Hadamard.  Take the surface's 
universal cover -- which is to say the upper half plane.  Tile it with fundamental domains for said surface's fundamental group (relative to a fixed const neg curv metric).  These
have some number of edges, a, b, c, ... . Now count how a geodesic crosses the edges:
acbaf... thus getting an (infinite) word -- or symbol sequence--  in the edges.  Theorem: the symbol sequence  is periodic if and only if the geodesic is. Theorem:  if we are given a (variable) negatively curved metric on the surface
then the symbol sequence uniquely determines the geodesic.  Theorem: if a sequence $s_N$ of 
symbol sequences converges to a symbol sequence $s$, in the sense that for any sufficiently large `window' L of word length centered around 0, the finite word of length L of arbitrary
length eventually agree, then the corresponding geodesics also converge.   Now,
approximate your given geodesic -- ie symbol sequence -- by a periodic sequence. 
symbol sequence by longer and longer periodic sequences.    
A: Of course closed geodesics can be explicitly constructed in the fundamental polygon by making sure that the angles at the end points match so that we get a closed geodesic rather than a geodesic loop.
The question of which immersed curves can be isotoped to a closed geodesic on a hyperbolic surface is quite subtle. I do not know the complete answer but the following paper may help: [Angenent, Sigurd B. Curve shortening and the topology of closed geodesics on surfaces.  Ann. of Math. (2)  162  (2005),  no. 3, 1187--1241.] The point is to start with a configuration of curves and use curve shortening flow to flow the configuration to a closed geodesic. 
A: There is a simple, geométrical construction of the closed geodesic freely homotopic to a given closed curve on the surface in John Stillwell's Geometry of surfaces. I'll not sketch the argument because his explanation even has pictures :P
A: Fix your favorite point in the surface.  Look at your favorite preimage $x$ of that point in the universal cover.  Now take all the lines going through that point and any other preimage (for each other preimage there is a unique such line).  Remember that all preimages are just the orbits of $x$ under the covering group $\Gamma$. Those are all the closed geodesics passing through your favorite point.
