To say that Wiles's proof of FLT is `seriously difficult to understand for non-mathematicians' is an understatement. It is seriously difficult to understand for any mathematician who has not spent a great deal of time studying certain very narrow bits of mathematics.
One thing that makes a proof elegant is generality. Another, as ymelup pointed out, is brevity and conciseness. There is also parsimony or conceptual simplicity, which is not the same thing as conciseness: a ten-line proof that involves four special cases may be brief, but is probably not elegant.
Of course, elegance, as an aesthetical judgement, is very subjective. Though mathematicians may agree that a particular proof is elegant (though such a concurrence of opinion is not by any means universal; I, for example, being an algebraist at heart, do not find geometrical proofs of the Pythagorean theorem very elegant), they will often have a hard time explaining why the proof is elegant—especially to non-mathematicians.