Let's start with the most elementary example: **projective space** $\mathbb P^n$. It's not hard to see that that the number of points on it is always $q^n + q^{n-1} + \dots + q  + 1.$

Note that this is because $\mathbb P^n$ can be always decomposed into simpler pieces: $\mathbb A^n \cup \mathbb A^{n-1}\cup\dots\cup \mathbb A^0$. Interestingly, something similar applies to **all $\mathbb F_q$-varieties**. Specifically, the Lefschetz fixed points formula from topology applied to arithmetics gives the following statement for a  variety $X/\mathbb F_q:$

> There exist some algebraic numbers $\alpha_i$ with $|\alpha_i| = q^{n_i/2}$ for some $(n_i)$ such that the number of points $$\\# X(\mathbb F_{q^l}) = \sum_i (-1)^{n_i}\alpha^l_i\quad \text{for}\\ l > 0 .$$

Numbers $\alpha_i$ in fact come from geometry: they are eigenvalues of some operators acting on etale cohomology groups $H_{et}(X)$. In particular, the numbers $n_i$ can only occupy an interval between 0 and $\text{dim}\\, X$ and there are as many of them as the dimension of this group.

These groups can directly compared to the case of $\mathbb C$ whenever you construct your variety in a geometric way. To see how, consider the example of curves. Over $\mathbb C$ the cohomology have the form $\mathbb C \oplus \mathbb C^{2g} \oplus \mathbb C\ $ for some $g$ called *genus*; the same holds over $\mathbb F_q$:

* **projective line**  $\mathbb P^1$ has genus 0, so it always has $n+1$ points
* **elliptic curves** $x^2 = y^3 + ay +b$ have genus 1, so they must have exactly  $n + 1 + \alpha + \bar\alpha$ points for some $\alpha\in \mathbb C$ with $|\alpha| = \sqrt q.$ This is exactly the **[Hasse bound](http://en.wikipedia.org/wiki/Hasse_bound)** mentioned in another post.  

These theorems, which provided an unexpected connecion between topology and arithmetics some half-century ago, were just the beginning of studying varieties over $\mathbb F_q$ using the geometric intuition that comes from the complex case. 


You can read more at any decent introduction to [arithmetic geometry](http://en.wikipedia.org/wiki/Arithmetic_geometry) or [étale cohomology](http://en.wikipedia.org/wiki/Etale_cohomology). There are also some questions here about [motives](https://mathoverflow.net/questions/tagged/motives) which are a somewhat more abstract version of the above picture.

----

As a reply to Ben's comment above about reconstructing the genus if you know $X_n = \#X(F_{q^n})$:

* You know with certainty that $1 + q^n - X_n = \sum \alpha_i^n\ $ for some algebraic numbers $\alpha_i, i = 1, 2, \dots $ having property $|\alpha_i| = \sqrt q.$

* There cannot be two different solutions $(\alpha_i)$ and $(\beta_i)$ for a given sequence of $X_n$ because if $N$ is a number such that both $\alpha_i = \beta_i = 0$ for $i>N$ then both $\alpha$ and $\beta$ are uniquely determined from the first $N+1$ terms of the sequence.

* So a given sequence uniquely determines the genus.

I don't know, however, if a constructive algorithm that guarantees to terminate and return genus for a sequence $X_n$ is possible. The first idea is to loop over natural numbers testing the conjecture that genus is less then $N$, but there seem to be some nuances.