There exists an injection from $X$ to $Y$ if and only if there exists a surjection from $Y$ to $X$.

There is no really elementary proof, since this is in fact independent of the "constructive" part of the usually axioms of set theory.

However if one has a basic understanding of the axiom of choice then one can easily construct the injection. The axiom of choice says that if we have a family of non-empty sets then we can choose exactly one element from each set in our family.

Suppose that $g\colon Y\to X$ is a surjection then for every $x\in X$ there is some $y\in Y$ such that $g(y)=x$. I.e., the set $\{y\in Y\mid g(y)=x\}$ is non-empty.

Now consider the family $\Bigg\{\{y\in Y\mid g(y)=x\}\ \Bigg|\ x\in X\Bigg\}$, by the above sentence this is a family of non-empty sets, and using the axiom of choice we can choose exactly one element from every set. Let $y_x$ be the chosen element from $\{y\in Y\mid g(y)=x\}$. Let us see that the function $f(x)=y_x$ is injective.

Suppose that $y_x=y_{x'}$, in particular this means that both $y_x$ and $y_{x'}$ belong to the same set $\{y\in Y\mid g(y)=x\}$ and this means that $x=g(y_x)=g(y_{x'})=x'$, as wanted.

Some remarks:

The above proof uses the full power of the axiom of choice, we in fact construct an inverse to the injection $g$. However we are only required to construct an injection from $X$ into $Y$, which need not be an inverse of $g$ -- this is known as The Partition Principle:

If there exists a surjection from $Y$ onto $X$ then there exists an injection from $X$ into $Y$

It is still open whether or not the partition principle implies the axiom of choice, so it might be possible with a bit less than the whole axiom of choice.

However the axiom of choice is definitely needed. Without the axiom of choice it is consistent that there exist two sets $X$ and $Y$ such that $Y$ has both an injection into $X$ and a surjection onto $X$, but there is no injection from $X$ into $Y$.

Suppose that $g$ is a surjection from $Y$ to $X$. For every $x$ in $X$, let $Y_x$ be the set of all $y$ such that $g(y)=x$. So $Y_x=g^{-1}(\{x\})$: $Y_x$ is the preimage of $x$. Since $g$ is a surjection, $Y_x$ is non-empty for every $x\in X$.

By the Axiom of Choice, there is a set $Y_c$ such that $Y_c\cap Y_x$ is a $1$-element set for every $x$. Informally, the set $Y_c$ chooses (simultaneously) an element $y_x$ from every $Y_x$.

Define $f(x)$ by $f(x)=y_x$. Then $f$ is an injection from $X$ to $Y$.

Remark: Fairly elementary, I guess, but definitely non-constructive. It can be shown that for general $X$, $Y$, and $g$, the result cannot be proved in ZF$. So we really cannot do better.

This requires the axiom of choice.

Suppose $g : Y \rightarrow X$ is surjective. Then $g^{-1}(x) \neq \emptyset$ for all $x \in X$. By the axiom of choice, there is a choice function $f$ such that for all $x$, $f(x) \in g^{-1}(x)$. $f(x)$ is then the desired injection $X \rightarrow Y$.

Technically, let $\mathcal{A} = \{g^{-1}(x) : x \in X\}$. The choice function is actually a function $\mathcal{A} \rightarrow \bigcup \mathcal{A}$. But I leave it to you to compose it with the appropriate function to get the desired $f$.