Countable union of countable sets is countable and AC (or axiom of countable choice) 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.
 A: 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.
A: In the absence of countable choice we need to make a clearer distinction between something being countable and it being counted, in the same way that in topology we distinguish between manifolds being orientable and being oriented. A countable set is a set for which there exists a bijection with $\mathbb{N}$ (what you call countable I call at most countable); a counted set is a set equipped with a bijection with $\mathbb{N}$. With this notion it is possible to rescue "a countable union of countable sets is countable" into a statement which requires no choice, namely

"a counted union of counted sets can be counted."

This amounts to the function $g$ being provided as part of the data rather than needing to be conjured up. It is almost always the case in practice that you can actually find countings reasonably explicitly so this is the result you're actually using anyway. 
