We know that for a group $G$ and a normal subgroup $H \triangleleft G$, the operation $g_1Hg_2 H := g_1g_2H $ is well-defined and in fact results in a group structure on $G/H$. Conversely, I want to show that if this operation is well-defined, my subgroup will in fact be normal.
To this end, I let $g_1, g_2 \in H$ and for some $h \in H$, $g_1' := g_1h, g_2' := g_2h$. Then we have
\begin{align} g_1g_2 H &= g_1 H g_2 H \\ &= g_1hH g_2hH \\ &= g_1'H g_2'H \\ &= g_1'g_2'H \\ &= g_1hg_2hH \\ &= g_1hg_2H. \end{align}
Hence there must exist some $\tilde{h} \in H$ such that $g_1g_2 = g_1hg_2\tilde{h}$, so $g_2 = hg_2\tilde{h}$, or $g_2\tilde{h}^{-1} = hg_2$.
Now if $g_2\tilde{h}$ was an arbitrary element of $g_2H$, we'd be done. However, since we've only shown that such an $\tilde{h} \in H$ exists, we're not.
Hence let $x \in g_2H$. Then there exists some $y \in H$ such that $x = g_2y$. What I want to show now is that there must also exist a $z \in H$ such that $x = zg_2$. I've tried this, but I didn't get any further:
\begin{align} x &= g_2y \\ &= g_2\left(\tilde{h}^{-1}\tilde{h}\right)y \\ &= hg_2 \tilde{h}y. \end{align}
Can anyone find me my $z$?
The definition $gH=Hg$ for all $g\in G$ is equivalent to $ghg^{-1}\in H$ for all $g\in G,h\in H$. So if $H$ is not normal then there are $g\in G$ and $h\in H$ such that $ghg^{-1}\notin H$. But that means $gHg^{-1}H\ne gg^{-1}H=H$. And it is obvious $gHg^{-1}H$ can't be equal to any coset which is not $H$. So we have to conclude it is not a coset at all.