From Zeta Functions to Curves Let $C$ be a nonsingular projective curve of genus $g \geq 0$ over a finite field $\mathbb{F}_q$ with $q$ elements. From this curve, we define the zeta function
$$Z_{C/{\mathbb{F}}_q}(u) = \exp\left(\sum^{\infty}_{n = 1}{\frac{\# C(\mathbb{F}_{q^n})}{n} u^n}\right),$$
valid for all $|u| < q^{-1}$. This zeta function extends meromophicially to $\mathbb{C}$ via the equation
$$Z_{C / \mathbb{F}_q}(u) = \frac{P_{C / \mathbb{F}_q}(u)}{(1 - u) (1 - qu)}$$
for some polynomial with coefficients in $\mathbb{Z}$ that factorises as
$$P_{C/\mathbb{F}_q}(u) = \prod^{2g}_{j = 1}{(1 - \gamma_j u)}$$
with $|\gamma_j| = \sqrt{q}$ and $\gamma_{j + g} = \overline{\gamma_j}$ for all $1 \leq j \leq g$. This last point tells us that $Z_{C / \mathbb{F}_q}(u)$ has a functional equation and satisfies a version of the Riemann hypothesis.
What happens if we run this construction in reverse? What if we start with a set of numbers $\gamma_j$, $1 \leq j \leq 2g$, such that $|\gamma_j| = \sqrt{q}$, $\gamma_{j + g} = \overline{\gamma_j}$ for all $1 \leq j \leq g$, and such that the polynomial
$$P(u) = \prod^{2g}_{j = 1}{(1 - \gamma_j u)}$$
has coefficients in $\mathbb{Z}$? Is there a way of telling whether the function
$$\frac{P(u)}{(1 - u) (1 - qu)}$$
is the zeta function of some curve $C$? Furthermore, what is this curve exactly?
A simple case of this is if we look at the function
$$\frac{1 - au + qu^2}{(1 - u) (1 - qu)}$$
for some $a \in \mathbb{Z}$ with $|a| \leq 2 \sqrt{q}$. How do we determine whether this function is the zeta function $Z_{C / \mathbb{F}_q}(u)$ of an elliptic curve $C$ over $\mathbb{F}_q$? If it is indeed equal to $Z_{C / \mathbb{F}_q}(u)$, what is the Weierstrass equation for $C$ (assuming $\mathrm{char}(q) \geq 5$)?
 A: To determine which potential zeta functions are actual zeta functions of curves is very difficult. The zeta function of a curve is determined by the zeta function of its Jacobian so one could instead ask which potential zeta functions are zeta functions of abelian varieties. This problem is solved (by Tate though as I recall Waterhouse was also involved in working out some details) and the answer is that essentially every $P(u)$ that could (i.e., having roots with the proper absolute values) occur with some extra restriction having to do with the endomorphism ring of the abelian variety having to be an order in a semi-simple algebra with some non-split factor. The conditions are anyway very explicit and reasonably easy to check. 
The next step is to pick out the zeta functions of principally polarised abelian varieties among all of them. This involves more arithmetic but is also also feasible.
The tricky part is the Schottky problem, to pick out the Jacobians among the principally polarised abelian varieties. This is in principle solved (at least in characteristic zero, I am less sure about positive characteristic) but any of the existing solutions meshes very badly with the problem of zeta functions as the solution to the problem above is very non-explicit and only tells you about the existence of a p.p.a.v. with given zeta function not a description of all of them.
Even where all of this can be done, for instance in genus $1$ where the Schottky problem is trivial, it is non-trivial to get actual equations. The reason for this is essentially that Tate's existence argument is through construction of a characteristic $0$ abelian variety with complex multiplication and then reducing it modulo $p$. Hence, the only way to be explicit would seem to be to first get the Weierstrass equation for the CM-curve. This is certainly possible (and fairly, for some definition of that term, efficiently) but it is far from easy. Of course, it still doesn't give all of the p.p.a.v.'s with given zeta function (though in some cases, for instance the ordinary case, all of them are the reduction of a CM abelian variety).
Addendum: As Noam points out there are a (small) number of general results excluding some zeta functions for curves where the p.p.a.v. exists. These generally concern improvements of the Weil bounds exploiting the fact that given the zeta function we can compute the number of points of the curve over the field and extensions of it and that these number should be non-negative and increase as the field increases (though the actual proofs are sometimes quite sophisticated). To see if the bounds obtained are sharp a lot of effort has also been expended on constructing specific curves with many points. In some cases special arguments can be used to exclude some values. See this site for tables and these slides for a description of a particularly detailed analysis of some cases.
A: In your last paragraph, you suggest that you are particularly interested in the case of elliptic curves. This is much easier than the general case, which is addressed well by Torsten's answer.
If $q$ is prime, and $|a| \leq 2 \sqrt{q}$, then there is always an elliptic curve with $\zeta$-function $(1-au+qu^2)/(1-u)(1-qu)$. This is the one dimensional case of Honda's theorem. I'll sketch the proof. As you will see, it uses some very sophisticated methods, and it will be very hard to make it effective.
Sidenote: What happens when $q = p^k$ for $k>1$? Then there are $2 p^{k-1}-1$ ways to choose $a$ to be $0 \mod p$. When $a=0$, the elliptic curve must be supersingular. But there are only $\approx p/12$ supersingular elliptic curves over $\mathbb{F}_{p^k}$. So, once $2 p^{k-1}$ is much greater than $p/12$, there will be $a$'s which don't occur. To be honest, I am not clear what happens if you feed one of these $a$'s into Honda's theorem.
Proof Sketch: Let $R$ be the ring $\mathbb{Z}[\phi]/(\phi^2 - a \phi + q)$. $R$ is an order in an imaginary quadratic field (the inequality $a^2-4q<0$ is used to show that this is an imaginary extension.) Let $K$ be the the fraction field of $R$ and let $H$ be its class field. Let $\mathfrak{p}$ be the ideal $(\phi)$ in $\mathcal{O}_K$. Since $\mathfrak{p}$ is principal, it splits in $H$; let $\mathfrak{q}$ lie over $\mathfrak{p}$. So $\mathcal{O}_H/\mathfrak{q} \cong \mathbb{F}_p$.
Let $E$ be an elliptic curve with complex multiplication by $R$; then $E$ can be defined over $H$. ($E$ is only well defined up to a quadratic twist, at this point.) Take a model of $E$ over $\mathcal{O}_H$. Let $E_0$ be the fiber over $\mathfrak{q}$. Then $E_0$ is an elliptic curve over $\mathbb{F}_p$. One can show that the Frobenius acts on $E_0$ by $\pm \phi$ or $\pm \overline{\phi}$, where the bar is the automorphism of $R$ over $\mathbb{Z}$ coming from complex conjugation. By changing the quadratic twist, one can make sure the sign is $+$. Then the trace of the Frobenius is $\mathrm{Tr}(\phi)$, which is $a$, as desired.
Sorry for making this so advanced, I don't know an easier way. I think you can find most of the tools I am using in Silverman's Advanced topics in the arithmetic of elliptic curves.
A: In the case of elliptic curves, a deterministic algorithm to find an elliptic curve $E/\mathbf{F}_p$ with a prescribed number of $\mathbf{F}_p$-rational points (and thus a prescribed zeta function) is described in R. M. Bröker's PhD thesis Constructing elliptic curves of prescribed order (see page 30).
It uses the idea explained in Torsten's answer, namely constructing a CM elliptic curve in characteristic 0 and then reducing it modulo $p$ (this idea dates back to Deuring). The algorithm computes some Hilbert class polynomial so is quite slow, it runs in time $O(p)$. It seems to be faster (but not deterministic anymore) to pick up random elliptic curves over $\mathbf{F}_p$ until one finds the right number of points. It seems to be an open problem to find an algorithm running in time polynomial in $\log p$.
