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$. 2 added 695 characters in body 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$O(\log p)$. 1 In the case of elliptic curves, a deterministic algorithm to find an elliptic curve$E/\mathbf{F}_p$with prescribed number of$\mathbf{F}_p\$-rational points (and thus a prescribed