In many cases it's much easier than you'd expect. See e.g. http://www.heinz.cmu.edu/~acquisti/ssnstudy/ (TL;DR: "we show that it is possible to predict individual SSNs simply from publicly available data").