I saw to prove that $a^2+b^2=c^2$ you can produce the algebraic solutions $a = x^2-y^2, b = 2xy, c = x^2+y^2$. To check that works just multiply it out but it produces infinitely many solutions when you set x and y to be integers.
Can you please show me more examples of this, especially if they show how to find the polynomials!
On
This site: A Collection of Algebraic Identities, seems to have a very good list of such solutions. Unfortunately, it does not seem to have any derivations, but it does give the name of the author in most cases (and sometimes, pdf files), so you should be able to track down the derivation if needed.
If you are looking for a general way to find such solutions, you are out of luck, I think.
Hilbert's tenth problem has been answered in the negative: there is no algorithm which determines if a solution to a general Diophantine equation exists.
Hope that helps.
Read the section "Rational points on conics" in the motivational chapter in the very beautiful book Rational points on elliptic curves by Silverman and Tate and/or google "rational parametrization of the circle". Also, once you have some knowledge of elliptic curves don't miss Franz Lemmermeyer's Conics - a poor man's elliptic curves which gives a beautiful treatment of Pell conics unified with theory of elliptic curves. Previously fragments of this theory were folklore scattered in pieces throughout the literature.