On the off chance you like graph theory, here is a silly use of the commuting graph to organize the count:
Let V be the collection of subgroups of G of prime order p. Let E be all pairs $(P,Q)$ where P and Q are subgroups of order p that commute: xy = yx for all x in P and y in Q.
Lemma: If $\langle x\rangle$ and $\langle y\rangle$ are not neighbors, then neither are $\langle x \rangle$ and $\langle x^{-i} y x^i \rangle$ for any $i$.
Proof: If $x x^{-i} y x^i = x^{-i} y x^i x$, then multiply $x^i$ on the left and $x^{-i}$ on the right to get $x y = y x. \square$
Since x has order p, that means any non-neighbor y actually gives p different non-neighbors.
Lemma: The non-neighbors of x come in batches of p.
That is pretty nice, since it means we can ignore most of the graph if we are only counting vertices mod p: we only need to look at the neighbors of x. It gets even better though:
Lemma: If x and z are neighbors, but y is not a neighbor of x, then $z^{-i}\langle y \rangle z^i$ is also not a neighbor of x.
The proof is actually the same as before, since we only used that $x$ and $x^i$ commuted in the previous proof, and now we use that $x$ and $z^i$ commute.
This means not only can we ignore non-neighbors of x, but we can choose another neighbor z of x, and ignore anyone who is not a neighbor of both x and z! Hopefully you see how we can continue:
Lemma: If X ⊆ V is a collection of vertices that are all mutual neighbors (a so-called clique), then the vertices that are not neighbors of all of them come in batches of p.
So we keep applying this until we get a maximal clique, and we know that everything outside of the clique comes in batches of p, so we just want to know how big a maximal clique is.
Lemma: A maximal clique is just (the order p subgroups of) an elementary abelian p-group, and in particular has $$\frac{p^k-1}{p-1} \equiv \frac{-1}{-1} = 1 \mod p$$ subgroups of order p, where $p^k$ is the size of the elementary abelian subgroup.
This finishes the problem. :-)
If g is any element of G, then $g^{-1}Pg$ is in V if and only if P is in V, and $(g^{-1}Pg,g^{-1}Qg)$ is in E if and only if $(P,Q)$ is in E, so of course G acts on the graph, but typically not vertex or edge transitively.
In case you like working examples first, here is a similar explanation, but making reference to a standard example of the symmetric group on 4 points.
As an example, when G is the symmetric group on 4 points, then $$V = \{ \langle(12)\rangle, \langle(13)\rangle, \langle(14)\rangle, \langle(23)\rangle, \langle(24)\rangle, \langle(34)\rangle, \langle(12)(34)\rangle, \langle(13)(24)\rangle, \langle(14)(23)\rangle \}$$
and the edges look like:

(source: uky.edu)
Now consider $g^{-1}Pg$ for g an element of order p. Either we get a new vertex, or $(\langle g \rangle, P)$ is an edge of the graph. If we get a new vertex, then it is easy to check we actually get p distinct vertices, none connected to $\langle g \rangle$, $P, g^{-1} P g, g^{-2} P g^2, \dots, g^{1-p} P g^{p-1}$.
For instance if we take $g=(14)(23)$ and $P=\langle(24)\rangle$, then we get both $P=\langle(24)\rangle$ and $g^{-1}Pg=\langle(13)\rangle$. So this g leaves 5 vertices alone, and swaps two pairs of vertices.
We thus have two very different kinds of vertices: the kinds that are connected to g, and the kinds that are not. The kinds that are not come in bunches of size p, so we can ignore them as we only are counting mod p. We thus can concentrate only on the neighborhood of g, which is normally called something like $\Lambda(C_G(g))$, but for us, it is just a bunch of stuff that commutes with g.
Here is a bit of trick that makes things almost too easy: what is so special about g? We still have this weird bowtie graph in the example, and honestly I prefer triangles. Well, I'll repeat the argument for $h=(12)(34)$, but since g and h commute, I still only have to consider the neighborhood of g (still the bow-tie). So we have three kinds of vertices: the kind that commute with g and h, the kind that commute with g but not h (and therefore h swirls them around in bunches of size p), and the kind that don't commute with g (and therefore g swirls them around in bunches of size p).
In other words, I can keep choosing neighbors until I am reduced to a complete subgraph (a clique), because people who don't know each other get put together in bunches of size p.
Once I am down to a complete graph, what do I have? Just a bunch of elements of order p that all commute with each other, so an elementary abelian group of order $p^k$ containing exactly $(p^k-1)/(p-1) \equiv (-1)/(-1) = 1 \mod p$ subgroups of order p.