It is written in tag page of Axiom of choice in MSE that
Countable union of countable sets is countable is a theorem which follows from AC. Do we really need AC to prove this? Please see following proof from Real Analysis by Bartle and Sherbert. I am not able to figure out if I am using AC here or not.
Theorem If $A(m)$ is a countable set for each $m\in\mathbb{N}$, then the union $A := \bigcup_m A(m)$
is countable.
Proof. For each $m\in\mathbb{N}$, let $f(m)$ be a surjection of $\mathbb{N}$ onto $A(m)$. We define $g: \mathbb{N} \times \mathbb{N} \to A$
by $g(m,n) := \{f(m)\}(n)$.
We claim that $g$ is a surjection. Indeed, if $a \in A$, then there exists a least $m \in \mathbb{N}$ such that $a$ is in $A(m)$ whence there exists a least $n \in\mathbb{N}$ such that $a = \{f(m)\}(n)$. Therefore, $a = g(m,n)$.
Since $\mathbb{N}\times\mathbb{N}$ is countable, it follows from the following theorem that there exists a surjection $f : \mathbb{N} \to \mathbb{N}\times\mathbb{N}$ whence $g\circ f$ is a surjection of $\mathbb{N}$ onto $A$. Now again apply the following theorem to conclude that $A$ is countable.
Theorem The following statements are equivalent:
(a) $S$ is a countable set.
(b) There exists a surjection of $\mathbb{N}$ onto $S$.
(c) There exists an injection of $S$ into $\mathbb{N}$.
Proof. (a)$\implies$(b) If $S$ is finite, there exists a bijection $h$ of some set $\mathbb{N}_n$ onto $S$ and we
define $H$ on $\mathbb{N}$ by
$$
H(k) :=\begin{cases}
h(k), &\text{for $k = 1,\dots, n$,}\\
h(n), &\text{for $k > n$.}
\end{cases}
$$
Then $H$ is a surjection of $\mathbb{N}$ onto $S$.
If $S$ is countably infinte, there exists a bijection $H$ of $\mathbb{N}$ onto $S$, which is also a surjection of $\mathbb{N}$ onto $S$.
(b)$\implies$(c) If $H$ is a surjection of $\mathbb{N}$ onto $S$, we define $g : S \to \mathbb{N}$ by letting $g(s)$ be
the least element in the set $H(-1)(s) := \{n \in \mathbb{N}: H(n) = s\}$. To see that $g$ is an injection of $S$ into $\mathbb{N}$, note that if $s, t \in S$ and $n := g(s) = g(t)$, then $s = H(n) = t$.
(c)$\implies$(a) If $g$ is an injection of $S$ into $\mathbb{N}$, then it is a bijection of $S$ onto $g(S) \subset \mathbb{N}$.
and $g(S)$ is countable, whence the set $S$ is countable. Q.E.D.
Best Answer
Yes. We really need the axiom of choice. When you say "let $f(m)$ be a surjection" you have chosen a surjection, one of continuum many.
There are infinitely many sets in your union, so you had to make infinitely many choices. This is exactly where the axiom of choice is used.