You could do it all at once, but there’s nothing wrong with the idea of first proving that $X=A\cup B$ is countably infinite and then going on to prove that $X\cup C$ is as well. However, you’re off on the wrong foot in trying to prove that $X$ is countably infinite. Pairing up $A$ and $B$ isn’t going to help: what you need to do is pair up $A\cup B$ and $\Bbb Z^+$.
Writing $A=\{a_1,a_2,a_3,\dots\}=\{a_n:n\in\Bbb Z^+\}$ and $B=\{b_1,b_2,b_3,\dots\}=\{b_n:n\in\Bbb Z^+\}$ is a good start. Now let $X=A\cup B$. Informally you have $X=\{a_1,b_1,a_2,b_2,a_3,b_3\dots\}$, and it’s intuitive clear that this can be paired up with $\Bbb Z^+$:
$$\begin{array}{cc}
1&2&3&4&5&6&7&8&9&10&\dots\\
a_1&b_1&a_2&b_2&a_3&b_3&a_4&b_4&a_5&b_5&\dots
\end{array}$$
The problem is to express this clearly enough so that if someone asks what $55$ corresponds to, you can actually answer. If you examine the table above closely enough, it’s apparent that even numbers in the top line match up with $b$’s, and odd numbers with $a$’s, and a little more examination reveals the rule: $2n$ matches up with $b_n$, and $2n-1$ matches up with $a_n$. You can now express this as a bijection from $\Bbb Z^+$ to $X$:
$$f(n)=\begin{cases}
a_{\frac{n+1}2},&\text{if }n\text{ is odd}\\\\
b_{\frac{n}2},&\text{if }n\text{ is even}\;.
\end{cases}$$
Added: There is just one possible problem here: if the sets $A$ and $B$ are disjoint, all is well, but this $f$ will not be a bijection if some $a_i$ is equal to some $b_k$, i.e., if $A\cap B\ne\varnothing$. To get around this, you should replace $B$ by $B\,'=B\setminus A$. If $B\,'$ is finite, let $C'=B\,'\cup C$, and use the argument below to show that $A\cup C'$ is countably infinite. And if $B\,'$ is countably infinite, use it instead of $B$ in the argument above.
Now you need to prove that $X\cup C$ is countably infinite. Since we now know that $X$ is countably infinite, there’s no need to keep the notational baggage of $a_n$’s and $b_n$’s: let $X=\{x_n:n\in\Bbb Z^+\}$ (or, more informally, $\{x_1,x_2,x_3,\dots\}$). If $C=\varnothing$, then $X\cup C=X$ is certainly countably infinite, so we can assume that $C$ is non-empty, say $C=\{c_1,\dots,c_m\}$. Now the easiest way to list $X\cup C$ systematically is $\{c_1,c_2,\dots,c_m,x_1,x_2,x_3,\dots\}$. Lay out the correspondence with $\Bbb Z^+$ as we did above:
$$\begin{array}{cc}
1&2&3&\dots&m&m+1&m+2&m+3&\dots\\
c_1&c_2&c_3&\dots&c_m&x_1&x_2&x_3&\dots
\end{array}$$
It’s not too hard not to write down a bijection $g$ from $\Bbb Z^+$ to $X\cup C$:
$$g(n)=\begin{cases}
c_n,&\text{if }1\le n\le m\\\\
x_{n-m},&\text{if }n>m\;.
\end{cases}$$
Starting with two bijections,
$\quad f:\mathbb{Z^+} \rightarrow A, \; g:\mathbb{Z^+} \rightarrow B$
we can use recursion to define a function $h:\mathbb{Z^+} \rightarrow A \cup B$ as follows:
Set $h(1) = f(1)$.
Assume $h$ has been defined on the segment $[1,n)$ with $n \ge 2$ and define
$$
h(n)=\begin{cases}
f\bigr(\,\text{min}(\,f^{-1}\text{<}A \setminus h[1,n)\,\text{>})\,\bigr)\quad\text{if }n \text{ is odd}\\
g\bigr(\,\text{min}(\,g^{-1}\text{<}B \setminus h[1,n)\,\text{>})\,\bigr)\quad\text{if }n \text{ is even}\\
\end{cases}
$$
So by recursive definition we've specified our function $h:\mathbb{Z^+} \rightarrow A \cup B$.
One can use induction to show that $h$ is injective.
One can use induction to show that the range of $h$ includes $A$.
One can use induction to show that the range of $h$ includes $B$.
So $h$ is a bijection.
Best Answer
The proof is almost correct, and is actually a good way of approaching the problem. One small error is that $h$ is not actually bijective, since you can have $a_i=b_j$ for some $i, j$. However, $h$ is still surjective, which suffices to show the union is countable.