The proof of the pudding
To fully judge how effective something is you need to use it for its intended purpose.
'The proof of the pudding' is just shorthand for 'the proof of the pudding is in the eating'. That longer version makes sense at least, whereas the shortened version really doesn't mean anything - nor does the often-quoted incorrect variation 'the proof is in the pudding'. The continued use of that meaningless version is no doubt bolstered by the fact that the correct version isn't at all easy to understand.
The meaning become clear when you know that 'proof' here is a verb meaning 'test'. The more common meaning of 'proof' in our day and age is the noun meaning 'the evidence that demonstrates a truth' - as in a mathematical or legal proof. The verb form meaning 'to test' is less often used these days, although it does survive in several commonly used phrases: 'the exception that proves the rule', 'proof-read', 'proving-ground', etc. When bakers 'prove' yeast they are letting it stand in warm water for a time, to determine that it is active. Clearly, the distinction between these two forms of the word was originally quite slight and the proof in a 'showing to be true' sense is merely the successful outcome of a test of whether a proposition is correct or not.
'The proof of the pudding is in the eating' is a very old proverb. The Oxford Dictionary of Quotations dates it back to the early 14th century, albeit without offering any supporting evidence for that assertion. The phrase is widely attributed to Cervantes in The History of Don Quixote. This appears to be by virtue of an early 18th century translation by Peter Motteux, which has been criticised by later scholars as 'a loose paraphrase' and 'Franco-Cockney'. Crucially the Spanish word for pudding - 'budín', doesn't appear in the original Spanish text. It is doubtful that 'the proof of the pudding' was a figurative phrase that was known to Cervantes.
The earliest printed example of the proverb that I can find is in William Camden's Remaines of a Greater Worke Concerning Britaine, 1605:
"All the proof of a pudding is in the eating."
It is worth remembering that, as the phrase is quite old, the pudding wouldn't have been a sticky toffee pudding from the sweet trolley, but a potentially fatal savoury dish. In Camden's listing of proverbs he also includes "If you eat a pudding at home, the dog may have the skin", which suggests that the pudding he had in mind was some form of sausage. THE OED describes the mediaeval pudding as 'the stomach or one of the entrails of a pig, sheep, or other animal, stuffed with a mixture of minced meat, suet, oatmeal, seasoning, etc., and boiled'. Those of you who have ventured north of the border on Burns Night will recognize this as a fair description of a haggis - "the great chieftain o' the pudding-race", as Burns called it in the poem Address to a Haggis, 1786. Mediaeval peasants, faced with a boiled up farmyard massacre, might have thought a taste test to have been a wise choice.
See also: the List of Proverbs.