When can integers be written as the sum of squares?

From Pythagoras, to Fermat, to Legendre, mathematicians have been interested in representation of integers by sums of squares. Legendre's beautiful 4 square theorem states that any positive integer can be represented as the sum of 4 squares. For example 1+4+4+9=18. One easily checks that 7 cannot be written as the sum of 3 squares. How well can we do with two squares?