People often find the origin of this phrase puzzling -- wouldn't an exception disprove the rule? Some have argued that "proves" was used in its meaning "To make trial of; to try, test" (definition II in the Oxford English Dictionary).
But as best I can tell, the origin of the phrase is the legal principle that the statement of an exception shows that the rule is opposite in the cases not excepted. Here's what the OED tells us:
The legal maxim, ‘Exception proves (or confirms) the rule in the cases not excepted’ (exceptio probat regulam in casibus non exceptis), which is in its original form an example of sense 1, is commonly quoted as ‘The exception proves the rule’ ....
Here's an early English American case, Watson v. Alexander, 1 Va. 340 (1794): "The act excepts the cases of contracts for gold or silver coin, tobacco, or other specific property; and if it be true, that an exception proves the rule, we must decide that all other contracts are within the law." And here's an illustration given by the OED that shows the meaning beyond the legal context; it's from Samuel Johnson's preface to a 1765 edition of Shakespeare (emphasis added):
It has been much disputed, whether Shakespeare owed his excellence to his own native force, or whether he had the common helps of scholastick education, the precepts of critical science, and the examples of ancient authours.
There has always prevailed a tradition, that Shakespeare wanted learning, that he had no regular education, nor much skill in the dead languages. Johnson, his friend, affirms, that he had small Latin, and no Greek; who, besides that he had no imaginable temptation to falsehood, wrote at a time when the character and acquisitions of Shakespeare were known to multitudes. His evidence ought therefore to decide the controversy, unless some testimony of equal force could be opposed.
Some have imagined, that they have discovered deep learning in many imitations of old writers; but the examples which I have known urged, were drawn from books translated in his time; or were such easy coincidences of thought, as will happen to all who consider the same subjects; or such remarks on life or axioms of morality as float in conversation, and are transmitted through the world in proverbial sentences....
There are a few passages which may pass for imitations, but so few, that the exception only confirms the rule; he obtained them from accidental quotations, or by oral communication, and as he used what he had, would have used more if he had obtained it.
The Comedy of Errors is confessedly taken from the Menæchmi of Plautus; from the only play of Plautus which was then in English. What can be more probable, than that he who copied that, would have copied more; but that those which were not translated were inaccessible?
By "the exception confirms the rule," Johnson seems to have meant that "seeing the exception, and recognizing that it is an exception, confirms for us that there is a rule." And my sense is that in the modern day, the phrase -- when used effectively -- has roughly that meaning.