What is known about the highest power of a prime dividing the number of automorphisms of a $p$-group? I know that it is at least $p$ provided $p^2$ divides $|G|$, but can we say more in some instances?
There is one obvious bound. By sending each $g\in G$ to its associated conjugation map, $[G:Z(G)]$ divides $|\text{Aut}(G)|.$
About this, I have three things that come to my mind. But just to make sure we are on the same page, I recall some definitions. The mapping sending any element $g\in G$ on its associated conjugation map has its image in $Aut(G)$. The image is isomorphic to $G/Z(G)$ and we note it $Int(G)$. It can be checked "by hand" that $Int(G)\triangleleft Aut(G)$. The outer automorphism group of $G$ is, by definition, $Out(G):=Aut(G)/Int(G)$. The three things we can say are the following :
Related to this you have two conjectures (well, I don't know the state of the art... but they used to be conjectures when I have heard about this topic) :
A conjecture from Berkovich. Let $G$ be a $p$-group of cardinal $>p$. Does there exist an automorphism of $G$ which is not in $Int(G)$ and of order exactly $p$?
The divisibility conjecture. Let $G$ be a non-cyclic $p$-group of order $>p^2$ then $|Z(G)|$ divides $|Out(G)|$ (equivalently $|G|$ divides $|Aut(G)|$).
$\textbf{Reference}$ : Geir T Helleloid A Survey on Automorphism Groups of Finite p-Groups; arXiv:math/0610294 [math.GR]
Those conjecture are true for abelian groups and there is a lot of papers proving one conjecture or the other for some particular classes of groups. To finally answer your question, we can say more if we add conditions on $G$, e.g. nilpotent of rank 2, of maximal rank, cyclic center, center of index $p^{2}$ are among the conditions for which some of those results hold.