$\omega^\omega$ is countable because it is a union of a countable collection of sets, each of which is itself countable: $$\omega^\omega = \bigcup_{i<\omega} \omega^i$$
So it suffices to show that:
- A union of a countable collection of countable sets is countable.
- $\omega^i$ is countable whenever $i$ is finite.
(1) should be familiar to you; it is the usual Cantor argument for showing that the rationals are countable. If the countable sets are $S_0, S_1\ldots$ with elements $S_i = \{s_{i0}, s_{i1}, \ldots\}$, then we can enumerate the union of the $S_i$ as $s_{00}; s_{10}, s_{01}; s_{20}, s_{11}, s_{02}; s_{30}, \ldots$.
(2) is not hard either; you can prove the the product of two countable sets is countable (essentially as in the previous paragraph) and then show that since $\omega^{i+1} = \omega\times\omega^i $, countability of $\omega^{i+1}$ follows from that of $\omega^i$, which is enough to establish the result.
(You may want to look up the notion of cofinality. An ordinal $X$ has countable cofinality if it is a countable union of smaller ordinals. If those smaller ordinals are themselves countable, then $X$ is countable. So to show that $\omega^\omega$ is countable, it is enough to show that it has countable cofinality, which we can do by observing that it is the union of the countable ordinals $\omega^i$ for finite $i$.)
Then similarly if $C$ is some countable ordinal, $\omega^C$ is countable. For we can write some countable sequence $c_0, c_1,\ldots$ whose limit is $C$, and then $\omega^C = \bigcup \omega^{c_i}$ expresses $\omega^C$ as a countable union of countable sets. So not only are $\omega$ and $\omega^\omega$ countable, so are $\omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$. And then we can take the union of countable the sequence of countable sets $\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$ and conclude that this union, usually written $\epsilon_0$, is countable as well.
$\epsilon_0$ has the property that it is the smallest ordinal $x$ for which $x=\omega^x$. There is an infinite sequence of countable ordinals with this property, and their union is still countable.
There are quite a few countable ordinals, and some of them are very strange monsters. See for example Church–Kleene ordinal and the Feferman–Schütte ordinal.
HINT:
Prove by induction that the successor of a countable ordinal is countable; conclude that addition of countable ordinals is countable; conclude that a product of countable ordinals is countable; and finally conclude that the exponentiation of two countable ordinals is countable.
The idea behind all of these is the same: countable union of countable sets is countable.
(One can also do that directly, without appealing to the axiom of choice as above, but it does make life simpler.)
Best Answer
There is a lot of surprising subtlety here!
(As the author of the linked answer, I can tell you what I had in mind in that specific context: say that a "really absolute ordinal" is an ordinal $\alpha$ such that there is a formula $\varphi$ which defines $\alpha$ in all transitive models of $\mathsf{ZFC}$ and such that $\mathsf{ZFC}$ proves that $\varphi$ defines a countable ordinal. This is a sharpening of Notion $1$ below to include a countability assumption, which was important for the linked question but doesn't seem to be particularly important for your OP so I'm dropping it here. If you're curious, though, the supremum of the ordinals of this type is just $\omega_1^{L_{\min\{\alpha: L_\alpha\models\mathsf{ZFC}\}}}$.)
Throughout, I'll reason in a somewhat-strong background theory $T$ - say, $\mathsf{ZFC}$ + "Every set is contained in a transitive model of $\mathsf{ZFC}$."
Let's start with a simple notion:
This is however a fairly boring notion: the $\mathsf{ZFC}$-absolute ordinals are just the ordinals $<\alpha$ where $\alpha$ is the least ordinal with $L_\alpha\models\mathsf{ZFC}$. But in a sense, this $\alpha$ itself is defined in an absolute way! It's only in "pathologically small" transitive models that we fail to see $\alpha$.
Can we do better?
Here we get much more variety! For example, if $\theta$ is almost-$\mathsf{ZFC}$-absolute, then so is $\alpha_\theta$ = the $\theta$th index of a level of $L$ satisfying $\mathsf{ZFC}$. But at this point we have a separate problem:
It certainly shouldn't be! But if $\omega_1^L=\omega_1$, then - taking $c=\omega_1$ - we do have that $\omega_1$ is almost-$\mathsf{ZFC}$-absolute via the formula "$x$ is the smallest uncountable ordinal." At this point the role of our background theory $T$ comes into focus: in order to get a good theory of almost-absoluteness, we'll need $T$ to be rather strong ($\omega_1$ really shouldn't be almost-absolute, and thinking along these lines motivates including some large cardinal axioms in $T$). But at this point we're running into real issues of background theory strength vs. phenomenon being studied. And all of this hasn't even touched the question of what happens if we change the "subject" theory from $\mathsf{ZFC}$ to something else.