A formula for the number of isomorphism classes of curves over $\mathbf F_q$ is probably hopeless. As pointed out by Olivier Benoist and Qiaochu Yuan, the much more well behaved number is given by isomorphism classes weighted by their automorphism group, in other words, the groupoid cardinality of the groupoid $\mathcal M_g(\mathbf F_q)$:
$$ \# \mathcal M_g(\mathbf F_q) = \sum_{[C]/\cong}\frac 1 {\# \mathrm{Aut}(C)}$$
This is also the number of $\mathbf F_q$-points of the coarse moduli space. It has a cohomological interpretation (Grothendieck-Lefschetz trace formula) that reads
$$ \# \mathcal M_g(\mathbf F_q) = \sum_{k}(-1)^k \mathrm{Tr}(\mathrm{Frob}_q \mid H^k_c(\mathcal M_g,\mathbf Q_\ell)).$$
Thus finding a formula for the number of $\mathbf F_q$-points becomes a question about understanding the cohomology of $\mathcal M_g$ as an $\ell$-adic Galois representation.
For small $g$ all the cohomology will be of Tate type which means that $\# \mathcal M_g(\mathbf F_q)$ is a polynomial in $q$, but for large $g$ this will certainly fail to be true and it's then not really clear what it would mean to write down an explicit formula, as suggested by Joe Silverman. Here are the formulas for $g \leq 4$:
$$ \# \mathcal M_2(\mathbf F_q) = q^3$$
$$ \# \mathcal M_3(\mathbf F_q) = q^6+q^5+1$$
$$ \# \mathcal M_4(\mathbf F_q) = q^9+q^8+q^7-q^6$$
For the first of these, it's a classical fact that $\mathcal M_2$ has the rational cohomology of a point. Also for $\mathcal M_3$ and $\mathcal M_4$ one actually knows the cohomology and its Galois structure in each degree, not just the alternating sum of cohomology groups: see Looijenga's "Cohomology of $\mathcal M_3$ and $\mathcal M_3^1$" and Tommasi's "Rational cohomology of the moduli space of genus 4 curves". I don't know if $\#\mathcal M_5(\mathbf F_q)$ is in the literature but it's probably something one could figure out. But quite soon writing down an explicit formula is going to get hopeless.
One can also start putting in marked points. The number of $\mathbf F_q$-points of $\mathcal M_{1,n}$ and $\mathcal M_{2,n}$ are in a sense known for all $n$, see Getzler's "Resolving mixed Hodge modules on configuration spaces" and my preprint http://arxiv.org/abs/1310.2508 . Here it's also true that for $n$ large it's not a polynomial in $q$, but instead you find a polynomial expression in $q$ and certain traces of Hecke operators on elliptic and Siegel cusp forms. You might also be interested in papers of (various combinations of) Bergström, Tommasi, Faber, van der Geer...
Addendum, much later: The paper "On the number of curves of genus 2 over a finite field" by Gabriel Cardona determines the actual number of isomorphism classes of genus two curves over a finite field (of odd characteristic). The even characteristic case is treated in a companion paper.