c. 1300, "a kind of sausage: the stomach or one of the entrails of a pig, sheep, etc., stuffed with minced meat, suet, 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).
Other possibility is the traditional one that it is from Old French boudin "sausage," from Vulgar Latin *botellinus, from Latin botellus "sausage" (change of French b- to English p- presents difficulties, but compare purse (n.)). The modern sense 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 attested from 1590s.