For my purposes, you may want to interpret "best" as "clearest and easiest to understand for undergrads in a first number theory course," but don't feel too constrained.

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau. All it uses is the Chinese remainder theorem and Euler's formula $a^{(p1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument). Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x and x is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR. In more detail. First let me describe the three "obvious" halves:
The three products are then (letting P = (p1)/2 and Q=(q1)/2):
All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p1}{2} \frac{q1}{2}$ elements. QED 


The question asked for the nicest proof for a first undergraduate course. Has anyone who offered a proposal used their favorite choice in a course? (Obviously the suggestions referring to $K$theory or Hilbert symbols weren't suggested in that spirit.) I've taught an undergrad number theory class several times and initially I gave the Gauss sum proof. But I realized afterwards that to the students this truly comes out of nowhere (it seems too magical), so I hunted around for other proofs, preferably some which build on more basic ideas that I could present earlier in the course. The Eisenstein (sinefunction) proof doesn't fit that requirement, and Zolotarev seems too farout if the students have not had group theory (which most have not). So what else is available? There is a proof due to V. Lebesgue (not H. Lebesgue!) that is based on counting points on hyperspheres mod $p$. It can be found in IrelandRosen's book. For an odd prime $p$ and positive integer $n$, let $$N_n(p) = \#\{(x_1,\dots,x_n) \in ({\mathbf Z}/(p))^n : x_1^2 + \cdots + x_n^2 = 1\}.$$ This is the number of mod $p$ points on the sphere in $n$space mod $p$. Earlier in the course I have the students discover numerically that every number mod $p$ is a sum of two squares. That is, $$\#\{(x,y) \in ({\mathbf Z}/(p))^2 : x^2 + y^2 = a\}$$ is positive for every $a$ in ${\mathbf Z}/(p)$. This could be shown by the pigeonhole principle, since $x^2$ and $a  y^2$ each take $(p+1)/2$ values mod $p$ and thus have an overlap. But more precisely, if you look at examples, you quickly discover that this 2variable count is independent of $a$ when $a$ is nonzero (from a more adv. point of view, the independence is because the norm map on unit groups $(({\mathbf Z}/(p))[t]/(t^2+1))^\times \to ({\mathbf Z}/(p))^\times$ is a homomorphism so its fibers have the same size, but that is a crazy explanation in an elem. number theory course). Enough data suggest what that uniform value is for any nonzero $a \bmod p$, and then we prove that in class. With this 2variable count we return to the hypersphere count and get a simple recursive formula connecting $N_n(p)$ to $N_{n2}(p)$. If you let $n = q$ be an odd prime, the recursive formula involves $p^{(q1)/2}$ plus $N_{q2}(p)$ times a multiple of $q$, so $N_q(p) \bmod q$ involves $(\frac{p}{q})$. [Note: Although the application will use $N_q(p)$, you must think about $N_n(p)$ for general odd $n$ first since the recursion from $n$ back to $n2$ makes no sense in general when the number of variables is only an odd prime: $n2$ usually isn't prime when $n$ is.] At the same time, the set being counted by $N_n(p)$ is invariant under cyclic shifts of the coordinates. On the very first problem set I have the students discover numerically that the number of cyclic shifts of an $n$tuple is always a divisor of $n$. So when we let $n = q$ be an odd prime, $N_n(p) = N_q(p)$ is the number of constant $q$tuples on the unit sphere mod $p$ plus a multiple of $q$. A constant $q$tuple is basically counting whether or not $q \bmod p$ is a square. So $N_q(p) \bmod q$ is related to $(\frac{q}{p})$. In the two approaches to counting $N_q(p) \bmod q$, one involves $(\frac{p}{q})$ and the other involves $(\frac{q}{p})$. This implies the QR relation mod $q$, which is actual equality since $1$ is not $1 \bmod q$. One nice thing about this approach is that it can also be used to prove the supplementary law for $(\frac{2}{p})$, by counting $$\#\{(x,y) \in ({\mathbf Z}/(p))^2 : x^2 + y^2 \equiv 1 \bmod p\}$$ in two ways. First there is the exact formula for the count (not just mod $p$) which I mentioned before. Second, most solutions in this count come in packets of size 8 (permute coordinates and change signs to get 8 solutions out of one solution). The exceptions which don't fall into packets of size 8 (when $x$ is $\pm y$ mod $p$ or $x$ or $y$ is $0$ mod $p$) depend on whether or not 2 mod $p$ is a square (does $2x^2 \equiv 1 \bmod p$ have a solution?), and comparing these two formulas mod 8 implies the usual rule for $(\frac{2}{p})$. Since I am able to get the students to work on ideas that are used in the proof much earlier on during the semester (one doesn't need quadratic residues to numerically look at solutions of $x^2 + y^2 \equiv a \bmod p$, for instance), this proof nicely ties together things they have seen throughout the course. So that's why this is my vote for the best proof to give in an undergrad course. 


I'm a fan of Zolotarev's proof, although the proof by Gauss's lemma does have sentimental value. 


The proof involving Gauss sums always seemed the best to me. I'm going to run my own undergrad number theory students through that proof, right after we develop some experience with roots of unity. If you remove the constraint of accessibility to students of a first number theory course, then you can avoid computations with roots of unity altogether: By Galois theory (and some knowledge of discriminants), a square root of p or p lives inside of the cyclotomic field of index p. An examination of the action of a Frobenius element at q on this square root relates Legendre(p,q) to Legendre(q,p). 


The proof involving Gauss sums seems to be the most standard one. There is also Tim Kuniskys proof using only basic group theory, which for me makes the theorem a bit less misterious. 


I don't think anyone mentioned Eisenstein's classic proof. This presentation of it is pretty good. I find it clear and attractive, especially because it sort of avoids Gauss' Lemma (which is a clever gadget but somehow offputting). 


The following variant of a proof going back to V. Lebesgue and Eisenstein is due to Aurelien Bessard (2010). See also W. Castryck, A shortened classical proof of the quadratic reciprocity law, Amer. Math. Monthly 115 (2008), 550551. Let $p = 2m+1$ and $q$ be distinct odd primes and let $N$ denote the number of solutions of the equation $$ x_1^2 + \ldots + x_p^2 = 1 $$ in the finite field ${\mathbb F}_q$.



There's a nice proof that involves the computation of $K_2(\mathbb{Q})$ and the interpretation of $K_2$ as a universal symbol (i.e. a bilinear map $\mathbb{Q}^\times\times\mathbb{Q}^\times\to A$ for some abelian group $A$, written multiplicatively, satisfying $(a,1a)=1$) in Milnor's book on algebraic $K$ theory. The tame symbols are interpreted as Legendre symbols, and by universality of $K_2$ as a symbol Tate claims that this proof is essentially Gauss's original argument. I suspect that this argument can be generalized to other totally real number fields, but explicit computations of $K_2(F)$ aren't very easy for large discriminants. It's definitely not the easiest to understand, but at the moment, it's my favorite. 


A great proof, inspired by Zolotarev's paper mentioned above, can be found in a very nice paper by Duke and Hopkins. http://www.math.ucla.edu/~wdduke/preprints/dukemain.pdf. 


Gauss' original inductive proof is the most natural proof to me. It is a computationally based induction on the maximum of the two primes p and q, and is far and away the most natural. Here, natural does not mean easy or elegant. It means a proof that arises naturally from the numerical patterns. Gauss computes the special cases of quadratic reprocity in a table in the back of his "Disquisitiones" from which it is fairly easy to guess which numbers are residues or non residues of given prime. He carries out the examples of p=2,3,5, 7 and the patterns start to show clearly. He gives an induction proof for some of those cases, indicating the structure of the general induction proof. Admittedly, Gauss, himself, looked for other proofs. Nevertheless, the first proof shows WHY the theorem is true in a way which the subsequent clever proofs do not. 


Gauss' original proof is to be in Gauss' Disquisitiones (English translation published by Springer): the residues 1 and +1 on pages 7273, the residues +2 and 2 on pages 7377, +3 and 3 on pages7778, residues +5 and 5 on pages 7982, +7 and 7 on page 82...the general law of reciprocity is stated on page8788, and the proof is carried out on pp 8898. There is a very fine presentation of the Gauss' general inductive proof in the textbook Introduction to Number Theory by Daniel E. Flath, on pages 7780. I have given this proof (Gauss' treatment of the residues +2, 2, +3, 3, and Flath's version of the general proof) repeatedly in my classes in the University of Costa Rica and the students have responded quite positively. Finally it can also be found in Mathews, Number Theory, but uses properties of the Jacobi symbol. Gauss used and stated these properties, but did not introduce a separate definition, and of course never used the Legendre symbol. 


I don't really know who discovered this proof, but it's interesting. It is taken from Prof. Ram Murty's website: 


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 wellknown 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 straightforward to compute (without knowing what a Gauss sum is) a nontrivial 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. 


The easiest to understand line by line are the elementary proofs that go through Gauss' Lemma, and are likely to be seen in any elementary number theory book. I've never actually liked these proofs personally and prefer the one at the start of Serre's "A Course in Arithmetic" for a proof without many technical prerequisites (finite fields only from memory). Edit: Less elementarily, one could argue that any 'best' proof will necessarily be adelic, proving that the product of the Hilbert symbols over all places at rational arguments is 1. For a geometric example of such an argument, I'm going to throw out arXiv:0804.2142 and references therein, primarily because I don't know if there exists an analogous argument using a central extension of GL_1 in the number field case. 


Kevin Brown has a nice expository article Jewel of Arithmetic and Franz Lemmermeyer has compiled a list of all published proofs both of which are worth a look. Edit: I just thought I'd add that there are 224 published proofs in Franz Lemmermeyer's list, and if you are using frames and if your institution subscribes to the online version of Mathematical reviews or Zentralblatt, then the reviews will appear in one of the frames. 


I learned the following proof from JeanFrançois Mestre, it is a variant of Zolotarev's. For every prime number $p>2$, let $T_p\in\mathbf Z[X]$ be the monic polynomial such that $T_p(X+1/X)X^{(p1)/2}=(X^p1)/(X1)=1+X+\dots+X^{p1}$. The complex roots of $T_p$ are $x+1/x$, where $x$ is a primitive $p$th root of unity. The same holds in any field of characteristic $\neq p$. In a field of characteristic $p$, the only root of $T_p$ is $2$, with multiplicity $(p1)/2$. Let $p,q$ be two odd prime numbers, with $p\neq q$. The resultant $\mathop{\rm Res}(T_p,T_q)$ of $T_p$ and $T_q$ is an integer. Since these polynomials have no common root, this integer is nonzero. Since these polynomials have no common root in every field, in particular modulo every prime number, this integer is $\pm1$. Compute this resultant modulo $p$. One gets $\mathop{\rm Res}(T_p,T_q)\equiv (1)^{(p1)(q1)/4} T_q(2)^{(p1)/2}\equiv (1)^{(p1)(q1)/2} q^{(p1)/2}\pmod p$. Consequently, $\mathop{\rm Res}(T_p,T_q)=\epsilon \left(\frac qp\right)$, with $\epsilon=(1)^{(p1)(q1)/4}$. Similarly, $\mathop{\rm Res}(T_q,T_p)=\epsilon \left(\frac pq\right)$. Now, $ \mathop{\rm Res}(T_p,T_q) = (1)^{\deg(T_p)\deg(T_q)} \mathop{\rm Res}(T_q,T_p), $ hence the quadratic reciprocity law. 


I think my favorite proof that's accessible to undergrads is Eisenstein's proof using the sine function. If we raise the bar on the prerequisites though, my favorite proof (the one that I would give if someone demanded a proof!) is the one using basic algebraic number theory and Galois theory. That's largely because this is a family of ideas that is useful for much more than "just" proving quadratic reciprocity. 


Several people above have mentioned the proof above using Gauss sums. In a recent assignment for our Galois theory course, we were asked to prove quadratic reciprocity using Galois theory. I would like to remark that in determining the fixed field of degree 2 over $\Bbb{Q}$ corresponding to the subgroup of index $2$ in $\textrm{Gal}(\Bbb{Q}(\zeta_p)/\Bbb{Q})$, one does not need to know about Gauss sums. Instead notice that $\Bbb{Q}(\zeta_p)$ is the splitting field of $x^p 1$, so that the discriminant of this polynomial $(1)^{p(p1)/2}p^p$ is in $ \Bbb{Q}(\zeta_p)$. The discriminant can be computed easily using the Vandermonde determinant and some knowledge about power sums. Since the square root of the discriminant is a product of differences of roots, it too is in the splitting field. Hence we see that $\Bbb{Q}(\sqrt{\pm p })$ is the unique subfield of index 2 contained in $\Bbb{Q}(\zeta_p)$, depending on whether $p \equiv 1$ or $3$ mod $4$. Keith Conrad remarked above that in the usual proof using Gauss sums, we need to show that $1 \equiv 1 \mod(p\Bbb{Z}[\zeta_p])$ gives us our desired contradiction, or that $2/p \in \Bbb{Z}[\zeta_p]$ gives a contradiction. I believe one can do this without invoking anything about integral bases. Instead we can say by Proposition 5.1(iii) of Atiyah  Macdonald that $2/p$ is integral over $\Bbb{Z}$ and since $\Bbb{Z}$ is integrally closed in its field of fractions (the proof of which can be rephrased entirely without any commutative algebra) this forces $2/p$ to be an integer. But by assumption $p$ was a prime not equal to 2 so this is a contradiction. 


I found this connection with linking numbers very fascinating and this discussion of generalizations. 


I recommend Gauss's third proof with modifications by Eisenstein. In my opinion, it is by far the clearest and most straightforward proof of Quadratic Reciprocity even though it is not the shortest. The proof makes no use of any mathematical discipline other than elementary number theory. That is, it uses no abstract algebra or combinatorics. Its charm is that it uses the greatest integer function in an advanced way in place of any advanced theory. The proof uses the greatest integer function to express a variety of numbertheoretic concepts and statements involving integers mathematically. Then, using properties of the greatest integer function, the proof works with these concepts and statements concretely (by manipulating them mathematically) to achieve the result. Gauss invented the greatest integer function for his third proof of QR in 1808 for this very purpose. Since it was long and messy, it was simplified by Eisenstein in 1844. How a proof is presented by the author is also important. In my online text, "A Mathematical Analysis of the Greatest Integer Function", I include a full treatment of QR. For Gauss's third proof, I used Dence. His book, "Elements of the Theory of Numbers" is an advanced text and I felt that his presentation of the proof contained gaps. While his presentation might be appropriate for his objectives and target audience, I felt that it would seem more like an outline to undergraduate students. For this reason, when rewriting the proof, I took three measures to provide clarity. I put a lot of effort into closing every gap and providing a thorough explanation for certain parts, which accounts for a lot of its length. Since the proof has many components even after modifications by Eisenstein, I organized it by dividing it into subobjectives and providing subproofs for each. I also include all three latticepoint diagrams with a numerical example in full detail. So, if you want to savor Gauss's third proof with modifications by Eisenstein, then you want to read my online text at www.greatestintegerfunctionresearch.org. My online text is also an excellent resource for various topics in number theory and analysis and is chockfull of original research. 


Well, I certainly don't know all the different proofs presented here, but the "natural", unoriginal and very elementary one you'll find p. 7778 of Hardy and Wright "Theory of Numbers" (4th edition) is assuredly quite pleasant to teach... 

