Not an expert, but I do not think that you need an evolutionary explanation: birds are often not stupid, and can simply observe that nests with more cigarettes have less parasites.
But that's the beauty of Darwinism, whether the information is stored in the genes or in their culture (memetically) doesn't matter, the selection/amplification process is the same.
I wonder if they choose nesting material based on insulation properties also. Cigarette stubs are probably great for stuffing into cracks and it is known that plugging air gaps dramatically increases whole house/nest insulation value.