What does an outer automorphism look like? I am working on a project in my group theory class to find an outer automorphism of $S_6$, which has already been addressed at length on this site and others. I have a prescription for how to go about finding this guy, but I have a larger conceptual question - what does an outer automorphism really look like? Is there an intuitive way to understand the difference between an inner and an outer automorphism? Inner automorphisms have always seemed easier for me to understand since we have an explicit representation $ghg^{-1}$ for members of the group. I can also understand this representation in terms of the Rubik's cube - rotate an edge, rotate a perpendicular edge, and the rotate the other edge back (is not the same as just rotating the perpendicular edge). What does an "outer automorphism" look like?
 A: In some sense, you've basically figured out the key difference between the two.  The inner automorphisms are the easy automorphisms to construct.  Conjugating by an element is a way to produce an automorphism in any group.  So you go ahead and do that with your group $G$ to produce a bunch of automorphisms.
Now you're left with the question: are there any more?  Of course, if you find an automorphism $\phi$ that is not inner, then $\phi \circ \text{Inn}(g)$ will be an automorphism for any $g \in G$.  So we may as well try to classify the quotient $\text{Out}(G) := \text{Aut}(G) / \text{Inn}(G)$.  But at this point, there is no general approach that will work for all $G$.  You just have to get your hands dirty and start studying lots of example.
As you no doubt know, what makes $S_6$ so special is that it does have a non-trivial automorphism (essentially only one because $\text{Out}(G) \cong \mathbb{Z} / 2\mathbb{Z}$), yet no other $S_n$ has an outer automorphism.  All I've been able to do is marvel at how the universe allows an outer automorphism when $n=6$ but never for any other value of $n$.  But I don't have a better explanation besides an outer automorphism has been constructed for $S_6$ and it's also been proven that one cannot be constructed for any other $S_n$.
A: Another rather accessible example of an outer automorphism can be found on matrix groups: Look at the inverse transpose map
$$\operatorname{GL}(n,F) \to \operatorname {GL}(n,F), \quad A \mapsto (A^{-1})^\top.$$
It is an automorphism, and except from all cases with $n=1$ and $\operatorname{GL}(2,\mathbb F_2)$, it is is outer.
A: 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.
