As for everything else, so for a mathematical theory: beauty can be perceived but not explained.
Why are numbers beautiful? It's like asking why is Beethoven's Ninth Symphony beautiful. If you don't see why, someone can't tell you. I know numbers are beautiful. If they aren't beautiful, nothing is.
As the above quotations hopefully convey, precise definitions of mathematical beauty are elusive, yet most mathematicians strive for it nonetheless. Moreover, since beautiful mathematics tends to be the best mathematics, an appreciation of mathematical beauty forms part of the intuition necessary to find a way from conjecture to proof.
Unfortunately, typical experiences of mathematics at school probably do little to instill such appreciation. But then, a mathematician is unlikely to extract much pleasure from the "plug-and-chug" application of memorised facts that seems to make up typical algebra or calculus exercises at that level. Rather, mathematical beauty arises from the subjects strengths- abstraction, and the notion of proof. The power of a mathematical theory is not that we can see that it works for a specific example, but that we can prove it will work for any suitable example you throw at it. Such a proof works from assumptions to an unavoidable conclusion- to be a beautiful proof, it must do so in a remarkable, rather than routine, way.
The mathematician's patterns, like the painter's or the poet's must be beautiful; the ideas, like the colours or the words must fit together in a harmonious way. Beauty is the first test: there is no permanent place in this world for ugly mathematics.
G H Hardy, A Mathematician's apology
I remember one of my high school mathematics teachers writing on my report that I needed to work on my elegance. At the time, this seemed like a strange request: but elegance is probably the best way to describe the type of beauty that is traditionally desired for a proof. Mathematical elegance tends to arise from minimal complexity, avoiding an excess of assumptions, overworked notation or length. Whilst simplicity is desirable, a proof that uses one difficult idea in an ingenious way is more elegant than one that plods through the routine application of a dozen simple ideas.
The proofs of the ancient Greeks tended to fall into this category, and the mathematician Pál Erdös considered God (the Supreme Fascist, as he called him) to have a book containing all such elegant proofs; to have your work described as 'from the book' was the highest praise. Such work is what usually comes to mind when considering beautiful mathematical technique.
However, there is a competing approach to beautiful mathematics, and one that is perhaps becoming more inevitable as the subject becomes far more complicated than that which the Greeks studied. Independent of the proof itself, a result is considered particularly deep (and hence beautiful) if it ties together seemingly disparate branches of mathematics. Wiles' proof of Fermat's Last Theorem, for instance, will never win any prizes for simplicity, but is still considered beautiful for the way it deftly tied together algebra, geometry and number theory (Ian Stewart's comparisons to War and Peace seem apt).
Depth can also arise from abstraction; a result that depends on many conditions to hold may often be a routine application of those conditions; a beautiful result, on the other hand, will have far-reaching implications by having less assumptions. The more abstract your mathematical playground, the deeper the results you manage to prove there. For instance, aspects of real analysis can be understood as a special case of metric space theory, which is itself a special case of topology. Proving a result in purely topological terms is then more powerful than proving it merely for the reals, as it will cover other spaces too; whilst discovering what results can't be demonstrated topologically offers insight into what makes the reals special.
The Vorschlaghammer-Nuß error
Beauty in mathematics is seeing the truth without effort.
It is a mistake to try and combine these two approaches. Mathematical heavy lifting of the type employed by Wiles is accepted if it yields beautiful results, whilst beautiful proofs of short but sweet results score favourably for elegance. The application of an excessively powerful result to quickly prove an elementary one is considered poor style, however, and without careful attention to the foundations, may even lead to circular argument. Similarly, exhaustive methods tend to be frowned upon as offering little insight beyond confirming a result. This charge is particularly levelled against computer proofs such as that of the four colour theorem; whilst the use of computers in mathematics is rarely contentious, their brute-force nature means the results are unlikely to be considered beautiful.