There are two common interpretations of this phrase, neither of which captures the original meaning. The most common interpretation is that no rule is absolute: an exception to a rule confirms that the rule is actually a reasonable rule and not, say, a tautology.
Of course, this is silly, leading others to claim a different meaning. According to this second interpretation, 'prove' in this phrase means 'to test', as it does in the aphorism "The proof is in the pudding". That is, "X is the exception that proves the rule Y" means that X is an exception to Y, and that the existence of an exception strains the truth of the assertion Y, or even disproves it.
The original form of the phrase is (in Latin) "Exceptio probat regulam in casibus non exceptis" (the exception proves the rule in cases not excepted). Probare, like English 'prove', can mean either 'to test' or 'to establish as true'. The intended meaning is that, if someone states an exception to a rule, it implies there was a rule in the first place.
According to Fowler's Modern English Usage, the original legal sense of the phrase is as follows:
'Special leave is given for men to be out of barracks tonight till 11.00 p.m.'; 'The exception proves the rule' means that this special leave implies a rule requiring men, except when an exception is made, to be in earlier. The value of this in interpreting statutes is plain.