There is the "Futurama Theorem" (based on a television show by the same name) that might be interesting to them. Dr. Farnsworth created a machine that swaps the minds of two individuals (i.e. your mind would be in my body and my mind in your body). Unfortunately, the body builds up resistance after a swap, which prevents swapping the minds back directly (i.e. if you and I just switched minds, we could not switch back without one of us first spending time in someone else's body).
The question is, given a collection of jumbled up minds and bodies, how can you get them all back to normal?
Your students will quickly realize that extra "clean" bodies (individuals who haven't swapped minds with anyone) are needed, since a collection of just two people with swapped minds could never get back to normal. It turns out that, no matter the size of the collection or the permutation of minds, two extra "clean" bodies are sufficient to reverse the permutation.
Here's the proof that appeared in the show, which uses nothing other than basic facts about permutations:
You can also read about it at Wikipedia and CutTheKnot.
Since you're working on $S_6$ for class, I won't answer that one for you. But I have another easy example of an outer automorphism.
The Quaternion group $Q_8$ can be represented as $\{1, -1, i, -i, j, -j, k, -k\}$, where $ij=k$, $jk=i$, $ki=j$, and $ji=-k$, $kj=-i$, $ik=-j$. The $-1$ element acts pretty obviously on the rest, e.g. $(-1)j=-j$. I think conceptually this is an easy presentation to work with.
So, $Q_8$ has $4$ proper nontrivial subgroups: $Z=\{1,-1\}$ (which is characteristic, and equal to both the center and commutator subgroups), $I=\{1,-1,i,-i\}$, $J=\{1,-1,j,-j\}$, and $K=\{1,-1,k,-k\}$.
All of these subgroups are normal, so there is no element in $x \in Q_8$ for which $I^x=J$, for example. Perhaps an inner automorphism will permute elements nontrivially within those three subgroups, but it won't move the subgroups themselves.
However, it's pretty clear just from looking at $I$ $J$ and $K$ that there's no real difference between these subgroups. If we changed $i$'s name to $j$, $j$'s name to $k$, and $k$'s name to $i$, this wouldn't mess up the group in any way - so, we can expect that a mapping $\sigma:i\mapsto j, j\mapsto k, k\mapsto i$ defines an automorphism of $Q_8$. In other words, this outer automorphism permutes the set of subgroups $\{I,J,K\}$. As a matter of fact, the outer automorphism group of $Q_8$ turns out to be $S_3$, and acts by permuting this set of three subgroups.
EDIT: I wanted to add another thing, a heuristic I use when thinking about automorphisms in general. I find it helpful, for some reason, to think about contructing an isomorphism from $G$ to $G$ (as if $G$ were some different group I was trying to prove isomorphic to $G$). To me this is very intuitive especially when considering outer automorphisms, as inner automorphisms do have that concrete definition using group elements, but outer automorphisms don't. This helped me to better understand what "characteristic" subgroups are - for example, any automorphism (outer or not) of $Q_8$ had better map $-1$ to $-1$, because it's the only element that acts like that. The same holds for the center of any group, the commutator subgroup of any group, normal (and hence unique) Sylow subgroups, any term of the derived, upper central, lower central, fitting, or frattini series, and so on. Anything that is uniquely defined using only properties of the group must be fixed by any automorphism, because if $G$ is isomorphic to $G$, the isomorphism between them must send those subgroups to the same place. Note that, as the comment points out, this heuristic requires some additional thought when the group is not finite.
Best Answer
One can analyse Rubik's cube using Gap. See here. I am unsure if this is what you are looking for or not, but it starts by showing how to "see" your cube as a permutation group, and then analyses the permutations.
(Too see your cube as a permutation group, write numbers on all the cubies, apart from the $6$ centre cubies, and see what rotating each of the $6$ faces once does to these numbers.)