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.
My suggestion, if you have really worked through most of Hartshorne, is to begin reading papers, referring to other books as you need them.
One place to start is Mazur's "Eisenstein Ideal" paper. The suggestion of Cornell--Silverman is also good. (This gives essentially the complete proof, due to Faltings, of the Tate conjecture for abelian varieties over number fields, and of the Mordell conjecture.) You might also want to look at Tate's original paper on the Tate conjecture for abelian varieties over finite fields,
which is a masterpiece.
Another possibility is to learn etale cohomology (which you will have to learn in some form or other if you want to do research in arithemtic geometry). For this, my suggestion is to try to work through Deligne's first Weil conjectures paper (in which he proves the Riemann hypothesis), referring to textbooks on etale cohomology as you need them.
Best Answer
Lots of the answers are going to be of the form "read book X" so I'll start: Serre's Course in Arithmetic is the best conceivable answer to the question "where could I find a concise, clearly written compilation of results in arithmetic geometry that can be proved without advanced machinery?" It's really a beautiful book.
The kind words about my article are much appreciated.