Even on the level of sets, the idea that any compact Riemann surface gives rise to an algebraic curve over $\mathbf{Q}$ should feel resoundingly false. There are uncountably many compact Riemann surfaces and only countably many algebraic curves over $\mathbf{Q}$. 

I think you may be confusing one or more of the following statements:

First, although a compact Riemann surface does not necessarily give rise to an algebraic curve over $\mathbf{Q}$, an algebraic curve over $\mathbf{Q}$ does give rise to an algebraic curve over $\mathbf{C}$, simply by extending the base of your curve to $\mathbf{C}$. Then we have an equivalence of categories between Riemann surfaces with analytic maps and algebraic curves over $\mathbf{C}$ with algebraic morphisms. You can prove this with the Riemann Existence theorem, but this is true in much more generality by Serre's GAGA. For the analytic theory I like Rick Miranda's book, but there are lots of potentially great references as it's an extremely classical subject.

Then, which Riemann surfaces give rise to algebraic curves over $\mathbf{Q}$? Well, that's a complicated question, but the start of the answer is Belyi's Theorem:

> An algebraic curve $C$ over $\mathbf{C}$ is isomorphic to the base change of an algebraic curve over $\overline{\mathbf{Q}}$ if and only if there exists a finite map $C \to \mathbb{P}^1$ ramified only at 3 points.

You asked for references and at least with this one, Koeck's "Belyi's Theorem revisited" http://arxiv.org/abs/math/0108222 is pretty canonical.

Moving from $\overline{\mathbf{Q}}$ to $\mathbf{Q}$ is an exercise in Galois cohomology, and although you're talking about general algebraic curves, Chapter X and Appendix B of Silverman's Arithmetic of Elliptic Curves are as good as any.

If you want to bypass all of that and just be given an algebraic curve from on high, moduli spaces are great ways to do so! All you have to do is to cook up a functor taking schemes $S$ over $\mathbf{Q}$ to isomorphism classes of certain objects over $S$ and call it a "moduli problem." If the problem is rigid - there are no nonidentity automorphisms of the objects - then by certain general nonsense your moduli problem will be representable - i.e., will give rise to a scheme over $\mathbf{Q}$. If you pick the right problem, you get an algebraic curve over $\mathbf{Q}$.

Now it's worth noting that the moduli problems that Elkies references are not quite rigid. Still they are not so far from being rigid, so we can still get algebraic curves out of them. See Edidin's article for details on this process - http://arxiv.org/abs/math/9805101

Finally I'll make a note about S. Carnahan's comment: There is a little bit of a subtle issue which people are fond of "passing over in silence" - Moduli problems give algebraic curves over $\mathbf{Q}$, which give algebraic curves over $\mathbf{C}$, which give Riemann surfaces. Which Riemann surface? Well the Riemann surfaces that Elkies works with are chosen because over $\mathbf{C}$ they form certain analytic moduli spaces - so if we start off with "the analogue over $\mathbf{Q}$" we ought to get back to that very special quotient of upper half space, right? Well, we do, but there's something to prove here and that's been mentioned in comments on this site in the past - http://mathoverflow.net/questions/21755/is-there-a-schemetical-construction-for-modular-curves-over-the-rationals