For every permutation $\sigma$ of \{1,2,3,4,5,6\}, Lagrange Interpolation gives a polynomial of degree at most 5 with $p(x)=\sigma(x)$ for every $x=1,2,3,4,5,6$. Additionally, this polynomial is unique: assume that there exist two polynomials $p, q$ of degree $\leq$ 5 such that they map $\{1,2,3,4,5,6\}$ to the same permutation. Then $p-q$ is a nonzero polynomial of degree $\leq$ 5 with 6 distinct roots, a contradiction. Thus an upper bound for the answer is $6!=720$ polynomials. However, not every polynomial obtained by Lagrange interpolation is of degree 5 (for example, $p(x)=$ $x)$. We can count the number of invalid polynomials using finite differences. A polynomial has degree less than 5 if and only if the sequence of 5th finite differences is 0. The 5th finite difference of $p(1), p(2), p(3), p(4), p(5), p(6)$ is $p(1)-5 p(2)+10 p(3)-10 p(4)+5 p(5)-p(6)$; thus we want to solve $p(1)-5 p(2)+10 p(3)-10 p(4)+5 p(5)-p(6)=0$ with \{p(1), p(2), p(3), p(4), p(5), p(6)\}=\{1,2,3,4,5,6\}. Taking the above equation modulo 5, we get $p(1)=p(6)(\bmod 5) \Rightarrow\{p(1), p(6)\}=\{1,6\}$. Note that $1-5 p(2)+10 p(3)-10 p(4)+5 p(5)-6=0$ if and only if $6-5 p(5)+10 p(4)-10 p(3)+5 p(2)-1=0$, so we may assume that $p(1)=1$ and double our result later. Then we have \{p(2), p(3), p(4), p(5)\}=\{2,3,4,5\} and $-p(2)+2 p(3)-2 p(4)+p(5)=1$. The above equation taken modulo 2 implies that $p(2), p(5)$ are of opposite parity, so $p(3), p(4)$ are of opposite parity. We do casework on \{p(2), p(5)\}: (a) $p(2)=2, p(5)=3; 2 p(3)-2 p(4)=0$ is a contradiction (b) $p(2)=2, p(5)=5; 2 p(3)-2 p(4)=-2 \Rightarrow p(3)-p(4)=-1 \Rightarrow p(3)=3, p(4)=4$ (c) $p(2)=3, p(5)=2; 2 p(3)-2 p(4)=-2 \Rightarrow p(3)-p(4)=-1 \Rightarrow p(3)=4, p(4)=5$ (d) $p(2)=3, p(5)=4; 2 p(3)-2 p(4)=0$ is a contradiction (e) $p(2)=4, p(5)=3; 2 p(3)-2 p(4)=2 \Rightarrow p(3)-p(4)=1$ but \{p(3), p(4)\}=\{2,5\}, contradiction (f) $p(2)=4, p(5)=5; 2 p(3)-2 p(4)=0$ is a contradiction (g) $p(2)=5, p(5)=2; 2 p(3)-2 p(4)=4 \Rightarrow p(3)-p(4)=2$, contradiction (h) $p(2)=5, p(5)=4; 2 p(3)-2 p(4)=2 \Rightarrow p(3)-p(4)=1 \Rightarrow p(3)=3, p(4)=2$. Hence there are a total of $720-2(3)=714$ polynomials.