Let $p : X \to Y$ be a covering map, where $X$ is path-connected, $y_0 \in Y$ and $x_0 \in p^{-1}(y_0)$. Denote $p_*(\pi_1(X, x_0))$ by $G$. I need to
construct a bijection between $p^{-1}(y_0)$ and $G\setminus \pi_1(Y, y_0)$, i.e. the set of right cosets of the group of the covering in the fundamental group of the base space.
Let us take any point $x_1 \in p^{-1}(y_0)$. Since $X$ is path connected, let $s : I \to X$ be a path between $x_0$ and $x_1$. Set $\alpha = [p \, \circ \, s] \in \pi_1(Y, y_0)$ and define $\phi(x_1) = G\alpha$.
I have shown, that $\phi$ is well-defined and surjective, but I don't understand,
how to show that $\phi$ is injective.
Let $x_1$ and $x_2$ be two points in $X$ and $s_1, s_2 : I \to X$ are paths between $x_0$ and $x_1$ and $x_0$ and $x_2$ respectively. Set $\alpha_i = [p \, \circ \, s_i]$, $i = 1,2$ and suppose that $G\alpha_1 = G\alpha_2$. How do I then show that $x_1 = x_2$ ?
Suppose $x_1$ and $x_2$ are two points in $X$ and suppose $\alpha_1$ and $\alpha_2$ are as defined in your question. If $G\alpha_1 = G\alpha_2$, then $$ \alpha_1 . \alpha_2^{-1} \in G = p_\star(\pi_1(X, x_0)).$$
This means that there exists a loop $\gamma \in \pi_1(X, x_0)$ such that $p\circ \gamma$ is homotopic to $\alpha_1 . \alpha_2^{-1}$.
Using the standard lifting properties for covering spaces, we can lift $\alpha_1 . \alpha_2^{-1}$ to a path in $X$, starting at $x_0$. This lift of $\alpha_1 . \alpha_2^{-1}$ is of the form $s_1 \circ \tilde s_2$, where $s_1 $ is the same as the path $s_1$ from $x_0$ to $x_1$ defined in your question, and $\tilde s_2^{-1}$ is a path starting at $x_1$ such that $$p \circ \tilde s_2^{-1} = p \circ s_2^{-1}.$$
It is not immediately clear that my $\tilde s_2 ^{-1}$ is the same as your $ s_2^{-1}$, since my $\tilde s_2^{-1}$ starts at $x_1$ whereas your $s_2^{-1}$ starts at $x_2$. All we know at this stage is that the projection of $\tilde s_2$ down to $Y$ agrees with the projection of $s_2$ down to $Y$.
However, we can also lift the homotopy between $p \circ \gamma$ and $\alpha_1. \alpha_2^{-1}$. Doing so, we deduce that $\gamma$ is path-homotopic to $s_1 \circ \tilde s_2^{-1}$. In particular, this implies that the start-point of $s_1 \circ \tilde s_2^{-1}$ agrees with the start-point of $\gamma$, and the end-point of $s_1 \circ \tilde s_2^{-1}$ agrees with the end-point of $\gamma$.
Since $\gamma$ was chosen to be in $\pi_1(X,x_0)$, we know that $\gamma$ starts and ends at $x_0$. From this, we deduce that $s_1 \circ \tilde s_2^{-1}$ also starts and ends at $x_0$. Therefore, $\tilde s_2$ must be a path from $x_0$ to $x_1$.
But $\tilde s_2$ and $s_2$ are both lifts of $\alpha_2$, starting at $x_0$. By the uniqueness property for lifts, we deduce that $\tilde s_2 = s_2$. Since the end-point of $\tilde s_2$ is $x_1$ and the end-point of $s_2$ is $x_2$, we can finally conclude that $x_1 = x_2$.