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** 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 or étale cohomology. There are also some questions here about 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.