Chad, I am assuming that the result you desire is {"dog", "cat", "bird", "bird"}
In[1]:= Fold[DeleteCases[#1, #2, {1}, 1] &, data, sub]
Out[1]= {"dog", "cat", "bird", "bird"}
and putting another cat in the "sub" list we get
data = {"cat", "dog", "cat", "bird", "bird", "fish"};
sub = {"cat", "cat", "fish"};
In[2]:= Fold[DeleteCases[#1, #2, {1}, 1] &, data, sub]
Out[2]= {"dog", "bird", "bird"}
