How do we prove $n^n \mid m^m \Rightarrow n \mid m$?

This is false: $4^4$ divides $10^{10}$ but $4$ does not divide $10$.

No, your second implication holds only for squarefree $\rm\:n,\:$ namely

Theorem $\rm\quad n\in\mathbb N\:$ is squarefree $\rm\, \iff\, \forall\ m\in \!\mathbb N\!:\, n^n\: |\: m^{\:m} \Rightarrow\ n\:|\:m$

Proof $\ (\Rightarrow)\ \ $ If $\rm\:n\:$ is squarefree then prime $\rm\:p\:|\:n\:|\:n^n\:|\:m^m\ \Rightarrow\ p\:|\:m\:.\:$ So we conclude $\rm n\:|\: m\ $ since $\rm\:m\:$ is divisible by each prime factor of $\rm\:n,\:$ so also by their $\rm\:lcm =\:$ product $\rm = n.$

$(\Leftarrow)\ $ $\rm\ n\,$ not squarefree $\rm\:\Rightarrow n = a\, p^k,\:$ prime $\rm\:p\nmid a,\ k\ge 2\:.\:$ Let $\rm\: j\in\mathbb N,\ p^{k-1}\!\nmid j\:,\:$ e.g. $\rm\ j = 1$

Then $\rm\displaystyle\:\ m\: =\: k\:n+a\:p\;j\ \Rightarrow\ n^n =\: (a\:p^k)^n\ |\ (a\:p)^{k\:n}\ | \ m^m\ \:$ by $\rm\:\ ap\ |\ m \ge k\:n$

but $\rm\ n\nmid m,\ $ else $\rm\displaystyle\ n\:|\:a\:p\:j\ \Rightarrow\: p^{k-1}\:|\ j\:,\: $ contra choice of $\rm\ j$.

Remark $\ $ The counterexamples in the other answers are special cases of this:

E.g. $\rm\ k = 2,\ a = 1\ $ yields $\rm\: m = k\:n + a\:p\:j = 2\:n + p\:j\:,\ p\nmid j\:.\:$

Hence $\rm\:n = 4\:,\ p = 2\ $ yields $\rm\:m = 8 + 2\:j\:,\ 2\nmid j\:.\:$ So $\rm\: j= 1\:$ yields $\rm\:m = 10\ $ (Jyrki);

$\rm\, j = 3\:$ yields $\rm\:m = 14\ $ (link from Chandru = user9413).

$\rm\ n = a\:p^k = 3\cdot 2^2$ yields $\rm\:m = k\:n + a\:p\:j = 24 + 6\:j,\ 2\nmid j\:.\:$ So $\rm\:j = 7\:\Rightarrow\:m = 66\:$ (mixedmath).

Not quite. And here's why:

Note that $12 \not | \;66$. Also, $12 = 2^2 \cdot 3$ and $66 = 2 \cdot 3 \cdot 11$. But $12^{12} |\; 66^{66}$, because $66^{66}$ has 66 'different' factors of 2 and 66 'different' factors of 3, and $12^{12}$ has only 24 'different factors of 2 and 12 factors of 3.

So the fact that $a \not | \;\;b$ does not imply that $a^a \not |\; \; b^b$. And I think that was the content of your question, right?