Interacting selectively and non-covalently with sulfate, SO4(2-), a negatively charged small molecule.