First note that
$$
^\omega2 := \sup \{ \underbrace{2^{2^{2^\ldots}}}_{n\text{-times}} \mid n < \omega \} = \omega.
$$
[..]but it seems a bit odd, that such a fast growing sequence is regarded as smaller than $\omega^2$.
Well, that's the thing when dealing with infinities. Sometimes our intuition fails us. While $(\underbrace{2^{2^{2^\ldots}}}_{n\text{-times}})_{n < \omega}$ could be regarded as "a fast growing sequence", each of its elements is finite and therefore $\omega$ is an upper bound. As $\omega$ certainly is the least upper bound, we get $^\omega2 = \omega$.
By an analogous argument we get that
$$2^\omega := \sup \{2^n \mid n < \omega \} = \omega$$
So we are left with ordering $\omega, \omega^2, \omega^\omega$ and $^\omega \omega$.
We have
$$\begin{align}\omega^2 &:= \omega \cdot \omega \\
&= \sup \{ w \cdot n \mid n < \omega\} \\
&\ge \omega \cdot 2 \\
&> \omega \end{align}$$
and
$$\begin{align}\omega^\omega &= \sup \{ \omega ^n \mid n < \omega \} \\
&\ge \omega^3 \\
&= \sup \{(\omega^2) \cdot n \mid n < \omega \} \\
&\ge \omega^2 \cdot 2 \\
&> \omega^2. \end{align}$$
Finally
$$\begin{align}^\omega \omega &:= \sup \{ \underbrace{\omega^{\omega^{\omega^ \ldots}}}_{n\text{-times}} \mid n < \omega \} \\
&\ge \omega^{\omega^\omega} \\
&= \sup\{\left( \omega^\omega \right)^n \mid n < \omega \} \\
&\ge \left(\omega^\omega \right)^2 \\
&= \omega^\omega \cdot \omega^\omega \\
&= \sup \{\omega^\omega \cdot \alpha \mid \alpha < \omega^\omega \} \\
&\ge \omega^\omega \cdot 2 \\
&> \omega^\omega. \end{align}$$
Combining these calculations we get the desired order:
$$
\omega = 2^\omega = {^\omega} 2 < \omega^2 < \omega^\omega < ^\omega\omega
$$
In general, ordinal and cardinal arithmetic are very different beasts and every ordinal arithmetic expression using only ordinals $\le \omega$ is countable.
proof (sketch)
Take a countable transitive model $M$ of a large enough fracture of $ZFC$. Every ordinal expression using only ordinals $\le \omega$ can be computed correctly inside $M$ (<- this requires some work). As $M$ only contains countable ordinals (as it is transitive), the result follows.