Are they all separate objects?  (can you select them in object mode separately?)  If so, select one of them, go to the material tab and click the little arrows next to the material name and select ADD NEW.