Let A be a set whose elements are nonempty sets, and let $$B=\bigcup_{X\in A}X$$ Then, corresponding to every function $g:A\rightarrow A$, there exists a function $g^{*}:A\rightarrow B$ such that $g^{*}(C)\in g(C)$ iff The Axiom of Choice.
I have the idea to use this:
Suppose A is a set whose elements are mutually disjoint, nonempty sets, and let $$B=\bigcup_{X\in A}X$$ Clearly $A\subseteqq P(B)$, there is a function $r:P(B)\rightarrow A$ such that $r(C)\in C$ for each $C\in P(A)$;if $C=r(A)$ , it follows immediately that C is the required.
The axiom of choice, in its simplest form, states that if $A$ is a set of non-empty sets, then there is a function $f$ with domain $A$, such that $f(X)\in X$ for all $X\in A$. Easily, the range of such $f$ is a subset of $\bigcup_{X\in A}X$, or $B$ as you denote it.
Assuming the axiom of choice, then, fix a choice function $f$ from $A$. Now for every $g\colon A\to A$ we simply define $g^*$ to be $f\circ g$.
In the other direction, pick $g$ to be the identity function to fallback to the axiom of choice itself.