How do you prove that $n^n$ is $O(n!^2)$?

Use a multiplicative variant of Gauss's trick: $$ (n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n $$

This also follows straightforwardly from the simple inequality $$ e\bigg(\frac{n}{e}\bigg)^n \le n!, $$ which can be found here (Wikipedia).

Elaborating: From this inequality it follows in particular that $$ n!n! \ge \frac{{n^n n^n }}{{e^n e^n }} = \bigg(\frac{n}{{e^2 }}\bigg)^n n^n , $$ hence $$ n^n \le \bigg(\frac{{e^2 }}{n}\bigg)^n n!n!, $$ showing moreover that $n^n \in o(n!^2)$.

EDIT: Here (Math Central, Problem of the Month 100, December 2010) you can find five different proofs of the inequality $(n!)^2 > n^n $, for all $n \geq 3$ or $n \geq 8$.

EDIT: Actually, for the above proof it suffices to use the inequality $n! > (\frac{n}{e})^n$ (cf. the comments below), which is trivial noting that $$ e^n = \sum\limits_{k = 0}^\infty {\frac{{n^k }}{{k!}}} > \frac{{n^n }}{{n!}}. $$

Group factors $k$ and $n-k$. When is their product bigger than $n$?