If there are $g,k\in G$ with $g\notin H$ and $gH = Hk$, then for this particular $g$ we have $gH = Hg$, or equivalently $gHg^{-1} = H$. This follows since under these hypotheses $g \in Hg \cap Hk = Hg \cap gH$, and two right cosets are either disjoint or equal.
Thus for the normalizer
$$N_G(H) = \{x\in G : xHx^{-1} = H\} \tag{$\ast$}$$
we know $g \in N_G(H)$, and consequently $H \subsetneqq N_G(H)$. Since
$$[G:H] = [G : N_G(H)] \cdot [N_G(H) : H]$$
is prime and $[N_G(H) : H] > 1$ by $(\ast)$ it follows that $[G : N_G(H)] = 1$, i.e. $N_G(H) = G$, in other words $H$ is normal.