Consider the action of ${\rm Aut}(D_4)$ on $D_4$ by $\psi \cdot g = \psi(g)$, where $D_4$ is the dihedral group on $4$ elements (so a square). I want to find the orbits of this action.
Instead of finding the elements of ${\rm Aut}(D_4)$, I thought that maybe I could use the fact that ${\rm Aut}(D_4) \cong D_4$.
I also started out by noting that for any $\psi \in{\rm Aut}(D_4)$, $\psi(r) = r $ or $r^3$ since the order must be the same, and the remaining generator $s$ maps to $sr, sr^2, sr^3$ or , $sr^4$, but not $r^2$ because then it can't generate $D_4$. But I am stuck and would appreciate any insight.
Thanks!
You are practically there. You just need to compile all the information together. By the way you have defined the group action, two elements $a$ and $b$ are in the same orbit if and only if there exists an automorphism $\phi$ such that $\phi(a) = b$.
Note that the identity $e$ will always get sent to itself. Thus, the orbit of the identity is just $$\{e\}$$
Next, you have noted that $r$ can only be sent to $r$ and $r^3$ by an automorphism. Thus, the orbit of $r$ is just $$\{r,r^3\}$$ There is nothing else in this orbit, otherwise this would imply $r$ could be sent to another element besides $r$ and $r^3$.
Similarly, we have that the orbit of $s$ is just $$\{s, sr, sr^2, sr^3 \}$$ since you have noted that these are the only elements $s$ can be sent to.
Lastly, we must have that the orbit of $r^2$ is just $$\{r^2\}$$ You have already noted that $r^2$ cannot be the image of $r$ and $s$ implying it cannot be in their orbits. Also, it is not in the orbit of the identity. Thus, the only option is for $r^2$ to be in an orbit by itself. You can check that any automorphism does indeed fix $r^2$.