c. 1300, "a kind of sausage: the stomach or one of the entrails of a pig, sheep, etc., stuffed with minced meat, suet, blood, and seasoning, boiled and kept till needed," perhaps from a West Germanic stem *pud- "to swell" (source also of Old English puduc "a wen," Westphalian dialect puddek "lump, pudding," Low German pudde-wurst "black pudding," English dialectal pod "belly;" also see pudgy).
The other possibility is the traditional one [also in Middle English Compendium] that it is from Old French boudin "sausage," from Vulgar Latin *botellinus, from Latin botellus "sausage" (the proposed change of French b- to English p- presents difficulties, but compare purse (n.)).
The sense of "dish consisting of flour, milk, eggs, etc., originally boiled in a bag until semi-hard, often enriched with raisins or other fruit" had emerged by 1670, from extension to other foods boiled or steamed in a bag or sack (16c.). German pudding, French pouding, Swedish pudding, Irish putog are from English. Pudding-pie as a type of pastry, especially one with meat baked in it, is attested from 1590s.