$\def\Irrep{\mathrm{Irrep}}\def\Conj{\mathrm{Conj}}\def\Out{\mathrm{Out}}\def\CC{\mathbb{C}}\def\Hom{\mathrm{Hom}}$Choose an element $g$ of $G$ not in $H$. Conjugation by $g$ is an automorphism of $H$. If we consider this automorphism as an element $\sigma$ of $\Out(H)$, then $\sigma$ is independent of the choice of $g$ and $\sigma^2=1$.
The outer automorphism group $\Out(H)$ acts on both the set $\Conj(H)$ of conjugacy classes of $H$ and the set $\Irrep(H)$ of (complex) irreps of $H$. Evaluation of characters gives a perfect pairing between $\CC^{\Conj(H)}$ and $\CC^{\Irrep(H)}$ which respects the $\Out(H)$ action, so $\CC^{\Conj(H)}$ and $\CC^{\Irrep(H)}$ are dual (and also isomorphic, since they are permutation representations) as representations of $\Out(H)$. Restricting our attention to the action of $\sigma$, we see that the number of orbits of orders $1$ and $2$ for $\sigma$ acting on $\Conj(H)$ and $\Irrep(H)$ must coincide. Let $a$ be the number of orbits of size $1$ and let $b$ be the number of orbits of size $2$. So $\#\Conj(H) = \# \Irrep(H) = a+2b$, and the number of $G$-conjugacy classes in $H$ is $a+b$.
Let $\epsilon : G \to \pm 1$ be the map with kernel $H$. Tensoring with $\epsilon$ is an involution of $\Irrep(G)$. It is "well known" that, if $V \cong V \otimes \epsilon$, then $V|_H$ decomposes as a direct sum of two irreps, forming an orbit for the $\sigma$ action and, if $V \not\cong V \otimes \epsilon$, then $V|_H$ is irreducible and fixed by $\sigma$. So $\#\Irrep(G) = 2a+b$. Of course, $\#\Conj(G) = \#\Irrep(G)$.
So the number of $G$-conjugacy classes in $H$ is $a+b$ and the number of $G$-conjugacy classes not in $H$ is $(2a+b) - (a+b) = a$. We have $a+b \geq a$ and we are done.
Proof of the well known claim. Let $\chi$ be the character of $V$. Note that the character of $V \otimes \epsilon$ is $\chi \epsilon$.
First, suppose that $V \cong V \otimes \epsilon$. Then $\chi(g)=\chi(g) \epsilon(g)$, so $\chi$ vanishes for all $g \not \in H$. Then $\sum_{g \in G} |\chi(g)|^2 = \sum_{h \in H} |\chi(h)|^2$, so we deduce that $\mathrm{Hom}_H(V,V)$ is $2$ dimensional and $V|_H$ must be a sum of two non-isomorphic irreps.
Now, suppose that $V \not \cong V \otimes \epsilon$. Then $\Hom_G(V, V \otimes \epsilon)=0$, so $\sum_{g \in G} \chi(g) \overline{\chi}(g) \epsilon(g)=0$ and we deduce that $\sum_{h \in H} |\chi(h)|^2 = \sum_{g \in G - H} |\chi(g)|^2$. Thus, $\sum_{h \in H} |\chi(h)|^2 = \tfrac{1}{2} \sum_{g \in G} |\chi(g)|^2$ and we deduce that $\Hom_H(V,V)$ is $1$ dimensional, so $V|_H$ is an irrep.