UK, 1882—‘penny’ refers to inexpensiveness, and ‘puzzle’ to the mysterious nature of the ingredients—perhaps also in humorous allusion to ‘penny puzzle’ in the sense of a puzzle-card sold on the street for one penny
1546—of little or no worth—here, ‘pudding’ refers to a sausage-like mass of seasoned minced meat, oatmeal, etc., stuffed into a prepared skin and boiled
USA, 1950, as ‘shopping-bag stuffer’—an advertising leaflet or similar piece of promotional material handed out to shoppers or placed in shopping bags alongside goods purchased
the fatty extremity of the rump of a goose, fowl, etc.—so called from the resemblance of this fatty extremity to the human nose—UK, 1826—earlier synonym: ‘pope’s nose’ (UK, 1788)