As the action is on a set of classes (necessarily dealt with by means of representatives), we have first to prove that the map is well defined, namely that $x'\in \mathscr C_x \Rightarrow \varphi\cdot\mathscr C_{x'}=\varphi\cdot\mathscr C_{x}$. This in indeed the case, because:
\begin{alignat}{1}
\mathscr C_{\varphi(x')} &= \{g\varphi(x')g^{-1}, g\in G\} \\
&= \{g\varphi(g'xg'^{-1})g^{-1}, g\in G\} \\
&= \{g\varphi(g')\varphi(x)\varphi(g')^{-1}g^{-1}, g\in G\} \\
&= \{(g\varphi(g'))\varphi(x)(g\varphi(g'))^{-1}, g\in G\} \\
&= \{g''\varphi(x)g''^{-1}, g''\in G\} \\
&= \mathscr C_{\varphi(x)} \\
\end{alignat}
where the last but one equality follows from $g\mapsto g\varphi(g')$ being onto $G$, for every $g'\in G$. Next, $\varphi\cdot\mathscr C_x\in \mathscr C$ by definition. Furthermore, $Id_G\cdot \mathscr C_x=\mathscr C_{Id_G(x)}=\mathscr C_x$. Finally, $(\varphi\psi)\cdot\mathscr C_x=\mathscr C_{(\varphi\psi)(x)}=\mathscr C_{\varphi(\psi(x))}=\varphi\cdot(\psi\cdot\mathscr C_x)$. So, this is indeed a group action and $\mathscr F(G)=\operatorname{Stab}(\mathscr C_x)$ is a subgroup of $\operatorname{Aut}(G)$. Then:
\begin{alignat}{1}
\psi\operatorname{Stab}(\mathscr C_x)\psi^{-1} &= \{\psi\varphi\psi^{-1}\mid \varphi\cdot\mathscr C_x=\mathscr C_x\} \\
&= \{\rho\mid (\psi^{-1}\rho\psi)\cdot\mathscr C_x=\mathscr C_x\} \\
&= \{\rho\mid \rho\cdot (\psi\cdot\mathscr C_x)=\psi\cdot\mathscr C_x\} \\
&= \operatorname{Stab}(\psi\cdot\mathscr C_x)
\end{alignat}
so $\mathscr F(G)$ is not normal in $\operatorname{Aut}(G)$. Rather, here we get that the stabilizers of the points of one same orbit are all conjugate to each other. Last, if $\varphi\in\operatorname{Inn}(G)$, then $\exists g\in G$ such that $\varphi\cdot\mathscr C_x=\mathscr C_{\varphi(x)}=\mathscr C_{gxg^{-1}}=\mathscr C_x$, whence $\varphi\in\mathscr F(G)$. Therefore, $\operatorname{Inn}(G)\le\mathscr F(G)$. (Note that this holds for every conjugacy class considered in $\mathscr F(G)$, and hence $\operatorname{Inn}(G)\le\operatorname{ker}\phi$, where $\phi$ is the homomorphism $\operatorname{Aut}(G)\to S_\mathscr C$ equivalent to your action.)
Comment. If the action is defined by $\varphi\cdot\mathscr C_x:=\mathscr C_{\varphi(x)}$, then the proof of the good definition focuses on the invariance w.r.t. representative's choice, being the membership of $\varphi\cdot\mathscr C_x$ to $\mathscr C$ trivial (by definition); this is the above approach. Conversely, if the action is defined by $\varphi\cdot\mathscr C_x:=\varphi(\mathscr C_x)$, then the proof of the good definition focuses on the membership of $\varphi\cdot\mathscr C_x$ to $\mathscr C$, being the invariance w.r.t. to representative's choice trivial (as $x'\in\mathscr C_x\Rightarrow \mathscr C_{x'}=\mathscr C_x$). The effort in both approach is the same, and equal to proving that $\varphi(\mathscr C_x)=\mathscr C_{\varphi(x)}$.
It is not true in general that $Z(G) = 1$ implies ${\rm Aut}(G) = {\rm Inn}(G)$.
There are many examples, for example $G = A_4$ has $Z(G) = 1$, but $[{\rm Aut}(G) :{\rm Inn}(G)] = 2$. In fact ${\rm Aut}(G) \cong S_4$ in this case. (For an example of an outer automorphism of $G$, take $f: G \rightarrow G$ defined by $f(x) = gxg^{-1}$ where $g = (12)$ is a transposition from $S_4$.)
In general describing automorphism groups is not always so easy.
For the question of how you would come up with $G = S_3$ as an example, as you note you should look for groups with $Z(G) = 1$. A good start for any problem is to look at some small examples, and it turns out in this case the smallest example works.
Best Answer
There are two properties which jointly guarantee that $G\to \operatorname{Aut}(G)$ is an isomorphism:
One can define the group of outer automorphisms $\operatorname{Out}(G) = \operatorname{Aut}(G)/G$ (so this is the cokernel of the map $G\to \operatorname{Aut}(G)$). Be careful that the name is slightly misleading: the set of outer automorphisms consists of all automorphism which are not inner (so not in the image of $G\to \operatorname{Aut}(G)$), so it is a subset of $\operatorname{Aut}(G)$ (and does not form a group), but the group of outer automorphisms is a quotient of $\operatorname{Aut}(G)$.
Then what you want is that $Z(G)$ and $\operatorname{Out}(G)$ are both trivial. Usually $Z(G)$ is easy to understand and compute, and for instance it is a very easy exercise to show that $Z(S_n)$ is trivial for all $n$ except $n=2$. On the other hand, $\operatorname{Out}(G)$ tends to be trickier to compute, and requires a finer understanding of $G$. For instance, it is a standard fact that $\operatorname{Out}(S_n)$ is trivial for all $n$ except $n=6$, but it is far less easy to prove, and the fact that there is an exception for $n=6$ (one of my favourite factoids about all of mathematics) should convince you that something tricky is going on.
So my point is that the crux of finding complete groups (groups such that $G\to \operatorname{Aut}(G)$ is an isomorphism) is to find groups with trivial outer automorphism group, and that just requires a detailed study of the group in question.
There are certain classes of groups that are guaranteed to be complete. For example, if $G$ is the automorphism group of a non-abelian simple group, then it is complete. An even deeper result is that if you start with a finite group $G_0$ such that $Z(G_0)$ is trivial, and define inductively $G_{n+1}=\operatorname{Aut}(G_n)$, then for $n$ large enough $G_n$ is complete. But that is difficult.