Solution:

Answer: $714$

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 $5$th finite differences is $0$. The $5$th finite difference of $p(1), p(2), p(3), p(4), p(5), p(6)$ is $p(1) - 5p(2) + 10p(3) - 10p(4) + 5p(5) - p(6)$; thus we want to solve $p(1) - 5p(2) + 10p(3) - 10p(4) + 5p(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) \pmod{5} \implies \{p(1), p(6)\} = \{1,6\}$. Note that $1 - 5p(2) + 10p(3) - 10p(4) + 5p(5) - 6 = 0$ if and only if $6 - 5p(5) + 10p(4) - 10p(3) + 5p(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) + 2p(3) - 2p(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$; $2p(3) - 2p(4) = 0$ is a contradiction

(b) $p(2) = 2, p(5) = 5$; $2p(3) - 2p(4) = -2 \implies p(3) - p(4) = -1 \implies p(3) = 3, p(4) = 4$

(c) $p(2) = 3, p(5) = 2$; $2p(3) - 2p(4) = -2 \implies p(3) - p(4) = -1 \implies p(3) = 4, p(4) = 5$

(d) $p(2) = 3, p(5) = 4$; $2p(3) - 2p(4) = 0$ is a contradiction

(e) $p(2) = 4, p(5) = 3$; $2p(3) - 2p(4) = 2 \implies p(3) - p(4) = 1$ but $\{p(3), p(4)\} = \{2,5\}$, contradiction

(f) $p(2) = 4, p(5) = 5$; $2p(3) - 2p(4) = 0$ is a contradiction

(g) $p(2) = 5, p(5) = 2$; $2p(3) - 2p(4) = 4 \implies p(3) - p(4) = 2$, contradiction

(h) $p(2) = 5, p(5) = 4$; $2p(3) - 2p(4) = 2 \implies p(3) - p(4) = 1 \implies p(3) = 3, p(4) = 2$

Hence there are a total of $720 - 2(3) = 714$ polynomials.