When an acid is added to water, why does the hydroxide ion concentration decrease? At equilibrium in pure water, we have
$$\ce{[H_3O+][OH-]} = 10^{-14}$$

Since $\ce{H3O+}$ and $\ce{OH-}$ ions are produced in pairs, we may conclude
$$\ce{[H_3O+]}=\ce{[OH-]} = 10^{-7}$$ 

So far so good. But shouldn't things change when we introduce a new substance into water ? I mean why does the first equation above hold no matter what ? 

Also when I introduce $\ce{H2SO4}$ into the water, it doesn't just give a $\ce{H+}$ ion, it also gives $\ce{HSO4-}$ ion. Shouldn't these new negative ions change the behavior of water? Why does my textbook never talk about these new negative ions? Help appreciated. Thanks!
As long as you stay in the dilute regime, that is if water molecules have most of the time to interact just with each other, $K_w$ won't change. Add 20% of anything soluble (salt, acid, alcohol, acetone, ...) and things look different.