Existence of how many sets is asserted by the axiom of choice in this case? Applying the axiom of choice to $\{\{1,2\}, \{3,4\}, \{5,6\},\ldots\}$, does only one choice set necessarily exist, or all of the $2^{\aleph_0}$ I "could have" chosen?  Or something in between?  It seems if only one, then I didn't really have much of a choice; I just had to take what the universe gave me.  But letting them all exist has its own problems.

In this case you don’t need the axiom of choice to get a choice function: just pick the smaller member of each pair. Various other choice functions are explicitly definable: we could just as well pick the larger member of each pair, for instance. Or we could pick the member that is divisible by $3$ if there is one, and the smaller one otherwise.
In general the axiom of choice gives you more than one choice function. Let $\{A_i:i\in I\}$ be a family of non-empty sets, and let $\varphi:I\to\bigcup_{i\in I}A_i$ be a choice function. For each $i\in I$ let 
$$B_i=\begin{cases}
A_i,&\text{if }|A_i|=1\\
A_i\setminus\{\varphi(i)\},&\text{otherwise}\;;
\end{cases}$$
then the axiom of choice gives us a choice function $\psi:I\to\bigcup_{i\in I}B_i$ for the family $\{B_i:i\in I\}$. This $\psi$ is clearly also a choice function for the original family, and it’s different from $\varphi$ unless every $A_i$ was a singleton. Eventually, once the appropriate cardinal arithmetic has been developed, one can prove that it gives us
$$\prod_{i\in I}|A_i|$$
choice functions.
