I Used Shift + L to select all objects in common.. how do I apply a material to all of those now?
You select all the objects that you want to apply material to, with the one that you already applied material to as the last selected one, then hit CTRL+L (make links) and choose Materials from drop down list.