Suppose $G$ is a finite non-abelian group, so that $|G|=p^n$ for some positive integer $n\ge 3$ (where $p$ is prime).
How can we prove that $|{\rm Aut}(G)|$ is divisible by $p^2$?
We know that $G/Z(G)\leq{\rm Aut}(G)$ by the inner automorphisms and the first isomorphism theorem. And because $G$ is non-abelian $Z(G)<G$ and by Lagrange's Theorem $|G/Z(G)|=\frac{p^n}{|Z(G)|}$. But from here I'm stuck.
As you correctly showed, $G/Z(G) \leq {\rm Aut}(G)$, so by Lagrange's theorem, $[G:Z(G)] \mid |{\rm Aut}(G)|$. Now, as $G$ is not abelian, $[G:Z(G)] > 1$. Since this is a $p$ group, that tells us that $p\mid [G:Z(G)]$ (and in fact that it is a power of $p$). But we want a factor of $p^2$, so let's suppose that $[G:Z(G)]=p$. $Z(G)$ is a normal subgroup of $G$, and because $p$ is prime, we have that $G/Z(G)$ is cyclic.
Let $G/Z(G) = \langle a Z(G) \rangle$. Then we can parition $G$ into the cosets $Z(G), a Z(G), a^2 Z(G), \dots, a^{p-1} Z(G)$. In other words, every element of $G$ takes the form $a^r g$ for some $r \in \mathbb Z$ and $g \in Z(G)$. Now, observe that $(a^r g)(a^s h)=(a^s h)(a^r g)$ as all the terms here commute: the powers of $a$ commute with each other and $g,h \in Z(G)$. So we have shown that if $G/Z(G)$ is cyclic then $G$ must have been abelian, a contradiction.
In summary, we have $p\mid [G:Z(G)]\mid |{\rm Aut}(G)|$. Furthermore, $[G:Z(G)]$ is a power of $p$ and the above showed that $[G:Z(G)]\neq p$. Thus, $p^2 \mid [G:Z(G)]\mid |{\rm Aut}(G)|$ as desired.