Plum, in this case, does not refer to the fruit, but is rather an adjective meaning "good"... maybe. Plum may also be a reference to sugarplums, which was simply a sweet sort of candy, or to the raisins that were often used to sweeten the pudding, and were sometimes referred to as plums.
A plum pudding is a sponge pudding made with fruit and brandy and sweetened with sugar, although the details have varied greatly over the centuries. Early recipes used beer and beef; sometimes the sugar is mixed in, sometimes poured on top; and they were traditionally boiled, but the Victorians preferred them steamed. They have always been highly spiced.