Let $\phi$ define a $*$automorphism from the matrix algebras $M_n(\mathbb{C})$ to $M_n(\mathbb{C})$ such that $\phi(I) = I$. Is it true that any such map $\phi$ can be represented as $\phi(x) = U x U^{\dagger}$ (where $U$ is a suitable unitary matrix)? If not, what is the most general expression?

Here is one generalization:
Using the fact that the algebra of compact operators is irreducible, this can be seen as a special case of:
A proof can be found for instance in Section 1.4 of Arveson's An invitation to C The first part is still true if you take all bounded operators instead of only the compact ones. (And these are the same thing in the finite dimensional case.) 


If $\phi$ is a $*$automorphism then $\psi:A\mapsto\phi(\overline A)$ is a $\mathbb{C}$automorphism. By the SkolemNoether theorem every $\mathbb{C}$automorphism of $M_n(\mathbb{C})$ is inner, that is of the form $\psi(A)=UAU^{1}$. This must commute with the $*$operation: $A\mapsto\overline{A}^t$. This leads to $UAU^{1} =\overline{U^t}^{1}A\overline{U^t}$ for all $A$. Thus implies that $U$ and $\overline{U^t}^{1}$ are the same up to a constant multiple. By multiplying $U$ by a constant we may make $U$ unitary. 


As an alternative to Robin Chapman's solution, I would like to state Exercise 7.8 from Rørdam's, Larsen's and Laustsen's "Introduction to the Ktheory of C*algebras":
If $A$ is the matrix ring, then $\mathrm{Aut}(K_0(A))$ is trivial and hence every automorphism of $A$ is approximately inner. Since $A$ is separable, every approximately inner automorphism is the pointwise limit of a sequence of inner automorphisms. And I think the finitedimensionality of $A$ implies that the pointwise limit of a sequence of inner automorphisms is again inner. Using the statement above, one immediately sees that, for instance, $\mathbb C\oplus\mathbb C $ possesses an automorphism which is not approximately inner. 


Another proof can be obtained using that $M_n(\mathbb{C})$ is singly generated (and finitedimensional). So $M_n(\mathbb{C})=C^*(s)$ for some $s$ (the shift, for example). Now, of course, $\phi(s)$ is a generator for the image. And by Spetch's theorem, $\phi(s)$ and $s$ are unitarity equivalent (because $\phi$ is multiplicative and it preserves the trace). Then there exists a unitary $U\in M_n(\mathbb{C})$ with $\phi(s)=UsU^{1}$. If you now take any $a\in M_n(\mathbb{C})$, we have $a=\sum_{j=0}^{n1} \alpha_js^j+\sum_{j=1}^{n1}\beta_j(s^*)^j$, for coefficients $\alpha_j,\beta_j$, and so $$ \phi(a)=\sum_{j=0}^{n1} \alpha_j\phi(s)^j+\sum_{j=1}^{n1}\beta_j\phi(s^*)^j $$ $$ =\sum_{j=0}^{n1} \alpha_j((UsU)^{1})^j+\sum_{j=1}^{n1}\beta_j(Us^*U^{1})^j=UaU^{1} $$ 


Yet another proof would be to consider a system $(e_{kj})$ of matrix units in $M_n(\mathbb{C})$, coming from some orthonormal basis (the canonical one, say). It is then easy to check that $(\phi(e_{kj}))$ is another system of matrix units, and so it corresponds to another orthonormal basis. The unitary implementing the change of basis is the one implementing $\phi$. 

