When did it become commonplace for data set providers to ask users to cite their paper(s)?
I don't see a logical distinction in citing used algorithms vis-a-vis data sets. Both seem perfectly natural to get cited. Both are an integral part in the results you are reporting in a paper and hence should be attributed. 

You're probably thinking in terms of machine learning papers, where typically a new method has to be benchmarked on a large variety of data sets. While it may seem like overkill to cite each and every data set that was used, lets not forget that whoever provided that data also put in effort and deserves credit for it. Again, this isn't that much different from citing the competing algorithms you are comparing against.

(Academic) software packages should also get cited, or at least mentioned, when they are used. This isn't really a new thing, for example the old 4-clause BSD license essentially demanded the same thing.