The number of $p$-subgroups of a group

This is Theorem of Frobenius (1895). The following proof is mixture of arguments of Wielandt, Krull and Gallagher.

Let $p^r$ be any divisor of $|G|$. Write $|G|=p^r.m$. Here $p$ may or may not divide $m$. Let $X$ be the collection of all subsets of $G$ of order $p^r$. Then $|X|=\binom{p^rm}{p^r} $. By orbit-stabilizer theorem $$ p^rm=|G|=|\mathcal{O}(A)|.|Stab(A)|.$$ Claim 1. If $1\in A$ then $Stab(A)\subseteq A$: \begin{align*} g\in Stab(A)\hskip2mm \Longrightarrow\hskip2mm gA=A \hskip2mm \Longrightarrow\hskip2mm g.1\in g.A=A \hskip5mm (\mbox{as }1\in A) \hskip2mm\Longrightarrow\hskip2mm Stab(A)\subseteq A. \end{align*}

Claim 2. $|Stab(A)|$ divides $|A|=p^r$.

Since for $g\in Stab(A)$ we have $gA=A$ hence $Stab(A).A=A$ which implies that $A$ (on RHS) is union of right cosets of $Stab(A)$, say $$Stab(A).a_1 \cup Stab(A) a_2 \cup \cdots \cup Stab(A).a_r=A.$$ Hence $|Stab(A)|$ divides $|A|=p^r$. This proves Claim 2.

Write $X$ as disjoint union of orbits,
$$X= \mathcal{O}(A_1) \cup \mathcal{O}(A_2)\cup \cdots \cup \mathcal{O}(A_t),$$ and we may assume that $1\in A_i$ for each $i$ (for, $A_i$, being subset of $G$, contains some $x\in G$ and then $\mathcal{O}(x^{-1}A_i)=\mathcal{O}(A_i)$ with $1=x^{-1}x\in x^{-1}A_i$.)

Claim 3. $\mathcal{O}(A_i)=m\Longleftrightarrow A_i$ is subgroup of order $p^r$.

Since $1\in A_i$, hence $Stab(A_i)\subseteq A_i$. Then, with Claim 1, $$ |\mathcal{O}(A_i)|=m \Longleftrightarrow |Stab(A_i)|=p^r=|A_i| \Longleftrightarrow Stab(A_i)=A_i.$$

Claim 4. $\mathcal{O}(A_i)=m \Longleftrightarrow \mathcal{O}(A_i)$ is coset space of subgroup $A_i$ (i.e. $\mathcal{O}(A_i)=G/A_i$).

If $\mathcal{O}(A_i)$ is coset space $G/A_i$, then $|\mathcal{O}(A_i)|=|G/A_i|=m$. Conversely, if $|\mathcal{O}(A_i)|=m$ then by Claim 3, $A_i$ is subgroup of order $p^r$, hence $\mathcal{O}(A_i)=\{gA_i\colon g\in G\}=G/A_i.$

By Claim 3 and 4, we have a bijection $$ \begin{Bmatrix} \mbox{orbits of order $m$}\end{Bmatrix} \longleftrightarrow \begin{Bmatrix}\mbox{ subgroups of order $p^r$} \end{Bmatrix}. $$ Note that if $|\mathcal{O}(A_i)|\neq m$ then $Stab(A_i)$ is proper subset of $A_i$, hence $|Stab(A_i)|$ strictly divides $p^{r}$, hence $|\mathcal{O}(A_i)|=|G|/|Stab(A_i)|=(p^rm)/|Stab(A_i)|$, which is divisible by $pm$.

Thus, if there are $k$ subgroups of order $p^r$, then there will be $k$ orbits of size $m$, say $\mathcal{O}(A_1)$, $\mathcal{O}(A_2)$, $\cdots$, $\mathcal{O}(A_k)$ and the other orbits have size divisible by $pm$. Then \begin{align*} X= \begin{Bmatrix} \mathcal{O}(A_1) \cup \cdots \mathcal{O}(A_k)\end{Bmatrix} \cup \begin{Bmatrix} \mathcal{O}(A_{k+1}) \cup \cdots \mathcal{O}(A_t)\end{Bmatrix} \end{align*} The first $k$ orbits have size $m$ and the remaining have size divisible by $pm$, hence $$\binom{p^rm}{p^r}=|X|\equiv km \pmod {pm}.$$ This congruence relation depends only on order of $G$; not on structure of $G$. Hence, in particular, if $G$ is cyclic (of order $p^rm$), then the number of subgroups of order $p^r$ is $1$ i.e. $k=1$, we get \begin{align*} |X|\equiv m \pmod {pm}. \end{align*} Thus $$km\equiv m \pmod {pm}, k\equiv 1 \pmod p.$$

(Thanks for the patience :))

I assume that you have proved Exercise 1C.8 of Isaacs' book Finite Group Theory that says that you can reduce the problem to $p$-groups.

Lemma 1. Let $H$ be a proper subgroup of a finite $p$-group $G$ and suppose $|H|=p^b$. Then the number of subgroups of order $p^{b+1}$ which contain $H$, is congruent 1 mod $p$.

Proof. Fix a subgroup $H$ of order $p^b$ of the $p$-group $G$. Since $H$ is normal and proper in $N_G(H)$, one can find a subgroup $K$ with $|K:H|=p$ (look at the center of $N_G(H)/H$, which is non-trivial, pick an element of order $p$, say $\overline{x}$ and put $K=\langle x \rangle$).
On the other hand, if $K$ is a subgroup of $G$ with $H \subset K$ and $|K:H|=p$, then $H \lhd K$ (because $p$ is the smallest prime dividing $|K|$), and hence $K \subseteq N_G(H)$.
We conclude that |{$K \leq G: H \subset K$ and $|K:H|=p$}| = |{$\overline{K} \leq N_G(H)/H: |\overline{K}|=p$}|. The lemma now follows from the fact that in the group $N_G(H)/H$ the number of subgroups of order $p$ is congruent to $1$ mod $p$ (in any group, which order is divisible by the prime $p$, this is true and follows easily from the McKay proof of Cauchy’s Theorem). $\square$

Lemma 2. The number of subgroups of order $p^{b-1}$ of a $p$-group $G$ of order $p^b$ is congruent 1 mod $p$.

Proof. Let $G$ be a non-trivial group of order $p^b$. Let $\mathcal{S}$ be the set of all subgroups of $G$ of order $p^{b-1}$. Observe that this set is non-empty and fix an $H \in \mathcal{S}$. We are going to do some counting on the set $\mathcal{S}$, by defining an equivalence relation $\sim$ as follows: $K\sim L$ iff $H \cap K=H \cap L$ for $K, L \in \mathcal{S}$.
Observe that for $K, L \in \mathcal{S}$ with $K \neq L$, $G=KL$, $K \cap L \lhd G$ and $|K \cap L|=p^{b-2}$. It is easy to see that the equivalence class $[H]$ is a singleton. In addition, $H=K$ iff $H \in [K]$ for $K\in \mathcal{S}$.
Now fix a $K \in \mathcal{S}$, $K \neq H$. Counting orders one can see that if $L \in \mathcal{S}$, then $H \cap K\subset L$ iff $L \in [K]$. Hence the number of elements in $[K]$ is exactly the number of subgroups of order $p^{b-1}$ containing $H \cap K$, minus 1, namely $H$. Owing to the previous lemma, we conclude that $|[K]| \equiv 0$ mod $p$. The lemma now follows. $\square$.

Using these two lemma's you now can prove the statement by cleverly counting the number of subgroup pairs $H$ and $K$ of $G$ having order $p^b$ and $p^{b+1}$ respectively. Now back to your original question

Theorem. Let $G$ be a group of order $p^a$, $p$ prime. Let $0 \leq b \leq a$ and $n_b=$|{$H \leq G: |H|=p^b$}|. Then $n_b \equiv 1$ mod $p$.

Proof. Let $H$, $K \leq G$, with $|H|=p^b$ and $|K|=p^{b+1}$. Define a function $f$ as follows: $f(H,K)=1$ if $H \subset K$ and $f(H,K)=0$ otherwise. Let us compute $\sum_{H} \sum_{K} f(H,K)$ in two different ways: $\sum_{H}$$\sum_{K} f(H,K) = \sum_{H} \sum_{H \subset K}1$ $\equiv \sum_{H} 1$ mod $p$, according to Lemma 1 above. Similarly, by reversing the order of summation of $H$ and $K$, the sum equals $\sum_{K} 1$ mod $p$, using Lemma 2. In other words, for all $b$, the number of subgroups of $G$ of order $p^b$ is congruent mod $p$ to the number of subgroups of $G$ of order $p^{b+1}$. The theorem now follows from the fact that the number of subgroups of order $p^a$ equals 1, namely $G$ itself. $\square$.

Remark. The theorem counts all subgroups of fixed order $p^b$. If we restrict ourselves to the normal subgroups of order $p^b$ the same holds: |{$H \unlhd G: |H|=p^b$}|$\equiv 1$ mod $p$. Sketch of proof: let $G$ act by conjugation on the set of all subgroups $H$ of order ${p^b}$. The fixed point are exactly the normal subgroups. Now apply the Theorem above.

Finally, also see this StackExchange entry.