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 $O(\log p)$\log p$.
