In Wikipedia there's a list of quite non-trivial and beautiful proofs of Fermat's two squares theorem. Actually I'm a bit surprised because this fact belongs to a very small set of mathematical fact that I, well, "see" and understand.
Here's how I'm approaching it: Let's assume that $a^2 + b^2 = p$, where $p$ is prime. For $p>2$ if $a^2$ is even, than $b^2$ is odd - and vice versa. A square can be even only if the original number is even, the same about an odd square. That actually means that we can rewrite as sum as $4n^2 + (2m + 1)^2 = p$.
This could be rewritten as $4(n^2 + m^2 + m) + 1 = p$. We actually hadn't use the fact that p is prime so far, only the fact that prime numbers are odd. Also we can notice that n should be even as well, i.e the even factor is divisible by four but not by any bigger power of two.
I do realize that it could not be that simple so I'm requesting for pointing out what atually I'm missing.