Why does a proof of $\exists f: X\to Y$ injection $\iff \exists g: Y \to X$ surjection requires the axiom of choice?

First of all the statement is not entirely true. If $X$ is empty, then there is always an injection into $Y$, but hardly ever a surjection from $Y$ onto $X$. But let's ignore that problem. So $X$ and $Y$ are always non-empty.

One direction of this theorem is just true without choice. If there is an injection $f\colon X\to Y$, then there is always a surjection from $Y$ onto $X$, since $f^{-1}$ is a bijection between a subset of $Y$ and $X$, so we can just extended to some fixed value outside the domain of that function (here we used the fact that $X$ is non-empty).

The other direction does in fact requires the axiom of choice. The easiest example, perhaps, is the case of Dedekind-finite sets.

Recall that $A$ is Dedekind-finite if whenever $f\colon A\to A$ is an injection, then it is a surjection; this is equivalent to saying that there is no injection from $\Bbb N$ into $A$. With the axiom of choice, $A$ is Dedekind-finite if and only if it is finite.

When the axiom of [countable] choice fails badly enough, it is consistent that there are infinite Dedekind-finite sets. But we can prove the following theorem:

There is a surjection from $A$ onto $\Bbb N$ if and only if there is an injection from $\Bbb N$ into $\mathcal P(A)$.

So suppose there is an infinite Dedekind-finite set $A$. If there is a surjection from $A$ onto $\Bbb N$, then this is an example for $X$ and $Y$ where there is a surjection from $Y=A$ onto $X=\Bbb N$, but there is no injection in the other direction. If there is no surjection from $A$ onto $\Bbb N$, then there is no injection from $\Bbb N$ into $\mathcal P(A)$, which means that $\mathcal P(A)$ is Dedekind-finite again, and there is always a surjection from the power set of an infinite set onto $\Bbb N$ (why?), so taking $Y=\mathcal P(A)$ and $X=\Bbb N$ works.

When investigating the usual proof for where the axiom of choice gets into play, you see that the axiom of choice is used to prove more. It is used to prove that if there is a surjection $g\colon Y\to X$, then there is an injection $f\colon X\to Y$ such that $g(f(x))=x$.

This "more" part in fact gives an equivalence to the axiom of choice itself. Since we really chose an arbitrary point from each fiber of $g$, and we really needed the full power of the axiom of choice for this sort of operation.

But what if we only wanted to prove that there is an injection? Well, as the above example shows you can't quite do it without some choice, and the above example can be generalized to show that any "bounded" part of the axiom of choice will not do. So maybe this statement is already equivalent to the axiom of choice itself? We don't know. The statement is called "The Partition Principle", and it is the oldest still-open problem in modern set theory, is it equivalent to the full axiom of choice?