There was some discussion above about how the proof with Gauss sums is hard to motivate. I disagree, but the motivation involves a little more (mild) algebraic number theory (i.e., Galois theory, algebraic integers, characteristic zero...) than appears in the shortened proof in Serre's book on arithmetic.

(This is of course well-known to number theorists, but I'll write up the full argument just in case somebody has only ever seen the more magical presentation with Gauss sums before.)

Let $p,q$ be odd, distinct primes below.

1) $\mathbb{Q}(\zeta_p)$ has Galois group $(\mathbb{Z}/p\mathbb{Z})^{\times}$, and therefore contains a unique subfield of degree $2$ over $\mathbb{Q}$. It's straight-forward to compute (without knowing what a Gauss sum is) a non-trivial element of this extension with rational square: it's the Gauss sum $G=\sum \(\frac{a}{p}\)\cdot(\zeta_p)^a$.

2) By construction, $G^2\in\mathbb{Q}$. What is it? It's easy to see from the formula above that $|G|^2=p$. Moreover, also by the formula, the complex conjugate $\overline{G}$ equals $G$ iff $p=1\mod 4$ and $\overline{G}=-G$ iff $G=3\mod 4$. Therefore, $G=\pm \sqrt{p}$ or $G=\pm\sqrt{-p}$ depending on the residue class of $p$ modulo $4$.

This is the major upshot: we have a very convenient expression for (a variant of) $\sqrt{p}$ now.

3) Note that $G$ is an algebraic integer. Therefore, we can reduce it modulo $q$. Since $\mathbb{Q}(G)$ is a quadratic extension of $\mathbb{Q}$ (namely: $\mathbb{Q}[\sqrt{\pm p}]$), the induced extension of $\mathbb{F}_q$ is an extension of degree $\leq 2$.

4) Is this extension $\mathbb{F}_q$ or the unique quadratic extension of $\mathbb{F}_q$? Well, it suffices to check whether or not $G\in\mathbb{F}_q$. To do this, you can use the Frobenius at $q$. It's easy to see in this way that $G^q=\(\frac{q}{p}\)\cdot G$ (by the formula for $G$). So the extension has degree one if $\(\frac{q}{p}\)=1$ and degree two if $\(\frac{q}{p}\)=-1$.

5) But since we know that $G=\sqrt{\pm p}$ (again: depending on the residue class of $p$ mod $4$), we see that we can give a second answer to the question in 4): $G$ defines an extension of degree $1$ if: a) $p=1\mod 4$ and $p$ is a quadratic residue mod $q$ or b) $p=3\mod 4$, $\sqrt{-1}\not\in\mathbb{F}_q$ (which is the same as $q=3 \mod 4$) and $\sqrt{p}\not\in\mathbb{F}_q$.

6) Comparing the answers to the above questions, we see that $q$ is a quadratic residue mod $p$ if and only if the conditions from 5) are satisfied. But these are exactly the conditions from quadratic reciprocity.