Zagier has a very short proof (MR1041893, JSTOR) for the fact that every prime number $p$ of the form $4k+1$ is the sum of two squares. 
The proof defines an involution of the set $S= \lbrace (x,y,z) \in N^3: x^2+4yz=p \rbrace $ which is easily seen to have exactly one fixed point. This shows that the involution that swaps $y$ and $z$ has a fixed point too, implying the theorem.

This simple proof has always been quite mysterious to me. Looking at a precursor of this proof by Heath-Brown did not make it easier to see what, if anything, is going behind the scenes. 
There are similar proofs for the representation of primes using some other quadratic forms, with much more involved involutions.

Now, my question is: is there any way to see where these involutions come from and to what extent they can be used to prove similar statements?

This paper by Christian Elsholtz seems to be exactly what you're looking for.  It motivates the Zagier/Liouville/Heath-Brown proof and uses the method to prove some other similar statements.  Here is a German version, with slightly different content.

Essentially, Elsholtz takes the idea of using a group action and examining orbits as given (and why not -- it's relatively common) and writes down the axioms such a group action would have to fulfill to be useful in a proof of the two-squares theorem.  He then algorithmically determines that there is a unique group action satisfying his axioms -- that is, the one in the Zagier proof.  The important thing is that having written down these (fairly natural) axioms, there's no cleverness required; finding the involution in Zagier's proof boils down to solving a system of equations.
