$\def\Irrep{\mathrm{Irrep}}\def\Conj{\mathrm{Conj}}\def\Out{\mathrm{Out}}\def\CC{\mathbb{C}}$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.