I don't want to type Greek letters hence I replaced $\gamma$ by $y$. Microsoft didn't replace them all.
Call the identity permutation $id$. Prove the contraposition: $\sigma \neq id \implies \exists \, y \in S_n : \sigma y \neq y\sigma.$
Suppose $\sigma \neq id.$ Then for some $1 \le x_1 \neq x_2 \le n, \; \color{brown}{\sigma(x_i) = x_2}$.
Because $n \ge 3$, hence there exists a third element $x_3 \neq x_2$ such that $y(x_2) = x_3$ and $\color{magenta}{y(x_1) = x_1}$.
Then $(σγ)(x_1) = σ(\color{magenta}{γ(x_1)}) = σ(\color{magenta}{x_1}) = x_2$
while $(γσ)(x_1) = γ(\color{brown}{σ(x_1)}) = γ(\color{brown}{x_2}) = x_3$,
so $σγ \neq γσ.$
(1.) How and why does $n \ge 3$ imply there exists $y \in S_n$ such that $y(x_2) = x_3$ and $\color{magenta}{y(x_1) = x_1}$ ?
(2.) How do you predestine, preordain to prove this by contraposition?
(3.) What's the intuition?
Update Fev. 4 2014: clem wrote $\color{darkred}σ: x_3 \mapsto i$.
Shouldn't this be $\color{darkred}{(γσ)^{−1} =σ^{−1}γ^{−1}} : x_3 \longmapsto i$ ? Hence I apply $γ^{−1}$ first to sally forth from $x_3 \to i$?
I think the intuition is present in the proof. I'm going to use very casual language, because to me that makes it more intuitively clear.
First, rewrite the condition as finding a $\sigma$ such that $y = \sigma^{-1} y \, \sigma$ for all $y \in S_n$.
Now assume that this holds for some permutation $y$. If $\sigma$ is not the identity, then some element will be moved by $\sigma$. In the proof, we call the element that is moved $x_1$ and we say that it "moves" to the place of $x_2$.
What if we had a $y$ that leaves the element $x_1$ where it was (equivalently, doesn't move $x_1$), and moves $x_3$ to $x_2$? If $n \geq 3 $ this gamma must exist. Because we are assuming the above condition holds, the complete operation $\sigma^{-1} y \, \sigma$ can't move $x_1$, because $y$ doesn't move it. But $\sigma$ moves $x_1$ to $x_2$, which is moved to $x_3$ by $y$. So $\sigma$ must move $x_3$ to $x_1$. But $x_2$ is already moved to $x_1$ by $\sigma^{-1}$, which contradicts the fact that $\sigma$ is a permutation. So if $\sigma$ is not the identity, ie if it moves something, then $y = \sigma^{-1} y \, \sigma$ cannot hold for all possible $y$ in $S_n$.
So the intuition is that we can always choose a $y$ that forces $\sigma$ to have two elements that are moved to the same 'spot' by the permutation, which is impossible. I'm not sure if this is intuition, but that's the best answer to "Why is this true?" that I can give.
Update to answer edited question
1) We need $n \geq 3$ because I name three elements $x_1$, $x_2$ and $x_3$. Since $S_n$ is just permutations, for y just use any permutation of n objects that swaps two objects and leaves at least one in the same position.
2) Because we are trying to prove that no other element with this property exists, a good first step (usually) is to assume such an element exists, then try to find a $\color{red}{contradiction}$.
$\color{red} { \text { But I queried contraposition, not contradiction? Hence this doesn't answer question 2? } }$
3) As for intuition, I'm not sure what else to say. For me, this becomes more clear if I imagine a game where I rearrange objects and my friend can rearrange them either before or after I do, but the answer has to be the same in both cases. Then it's clear that finding such a permutation would be quite difficult, so it's not surprising that it is not possible (other than the trivial rearrangement)