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.

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 \left(\frac{a}{p}\right)\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=\left(\frac{q}{p}\right)\cdot G$ (by the formula for $G$). So the extension has degree one if $\left(\frac{q}{p}\right)=1$ and degree two if $\left(\frac{q}{p}\right)=-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.