Theorem
Let $X$ be uncountable. Let $A$ be countable. Then $|X\cup A| = |X|$.
Proof
As $|X|>\aleph_0 \rightarrow \exists f: \Bbb N \to X$ injective.
Note that $\operatorname {Im}(f)=\{f(0)=x_0,f(1)=x_1,...\}= X' \subsetneq X$ and $|X'|=\aleph_0$.
Now $X=(X\setminus X')\cup X'$. (proof $|X'|=|X'\cup A|$). Then we define some bijection $G$ sending $X\setminus X' \to X\setminus X'$ and $X' \to X'\cup A_\square$.
My question is: Is choice being used when saying $\operatorname{Im}(f)=\{x_0,...\}$? My professor mentioned something about this, but I didn't really understand it as this was just a very preliminary set theory class for another subject and we never ended learning about choice.
Yes. You need the axiom of choice in order to prove that every infinite set has a countably infinite subset. And choice is used to prove there is an injective function in the first place. Once you have that injection, enumerating the image is choice free.
The axiom of choice is needed here because $X$ is any arbitrary set. In order to prove that there is an injection from $\Bbb N$ into $X$ we typically begin by choosing an arbitrary element $x_0\in X$, then choosing an arbitrary element $x_1$ of $X\setminus\{x_0\}$, and so on by recursion. But these elements are in fact arbitrary, what's worse is that the choice of $x_0$ affects the possible choices for $x_1$ and for $x_{42}$, and the choice of $x_{10^{100}}$ has to take into consideration all the previous $10^{100}$ choices.
So while we can show, by induction, that if we have an injection from $\{k\in\Bbb N\mid k<n\}$ into $X$, then we can extend that injection by one more step, in order to prove the existence of an injection from $\Bbb N$ into $X$ we want to somehow single out an entire sequence of selections. But these are arbitrary, and here is where the axiom of choice comes into play.
Mathematically speaking, we know that the axiom of choice is needed because there are models of set theory where the axiom of choice fails and there are infinite sets without a countably infinite subset.
This entire thing, of course, hinges on the definition of "infinite". If you take it to be "there is a self-injection which is not a bijection", then you don't really need the axiom of choice; but you lose the equivalence that a set is infinite if and only its cardinality is not equal to a natural number.
The standard definition of infinite, though, is "not finite" where "finite" is defined to have cardinality equal to a natural number. So in the standard setting, this theorem uses the axiom of choice.
Similarly, this depends on how you define uncountable. If you just define uncountable as $|A|>\aleph_0$, then again you don't need to appeal to the axiom of choice. But you lose the dichotomy of "an infinite set is countable or uncountable". As before, the standard definition of "uncountable" is "not countable" (or "not finite or countable", depending how you defined countable).