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
The set $S$ gives rise to a subscheme (which let's also denote by $S$) of $\mathbb{P}^1_{\mathbb{Z}},$ because relatively a prime pair $(x,y)$ corresponds to a section of $\mathbb{P}^1_{\mathbb{Z}}\rightarrow\operatorname{Spec}\mathbb{Z}$, and we take the union of these divisors in $\mathbb{P}^1_\mathbb{Z}$.
Now, we have a map $\mathcal{O}(d)_{\mathbb{P}^1}\rightarrow\mathcal{O}(d)_S,$ and it will suffice to show that for some $d$ some element in the image of the induced map on global sections is nowhere zero. (If one composes this map with the map $\mathcal{O}(d)_S\rightarrow\mathcal{O}(d)_{\operatorname{Spec}\mathbb{Z}}$ corresponding to a section $(x,y)$, one gets at the level of global sections the evaluation map $\mathbb{Z}[x,y]_d\rightarrow\mathbb{Z}$ on degree $d$ homogeneous polynomials.)
For this, it suffices that one can find $d$ so that this map is surjective on global sections and so that $\mathcal{O}(d)_S$ is trivial. The map will be surjective on global sections for large enough $d$ by ampleness of $\mathcal{O}(1)$, and the triviality of a power of $\mathcal{O}(1)_S$ follows from the finiteness of $\operatorname{Pic}(S)$.
It's maybe slightly inaccurate to say just that it's a case in Lemma 7.3 in the above paper; rather, this exact argument is ran in the proof of Corollary 1.3 (which immediately follows the aforementioned lemma) to prove a much more general result.