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).