Having worked on this problem before (the comparison to human performance they cite is from my work) and seeing all the recent successes of deep learning, I'd bet that a lot of the gain here comes from what deep learning generally provides: being able to leverage huge amounts of outside data in a much higher-capacity learning model.
Let me try to break this down:
In machine learning, when you have input data that is labeled with the kinds of things you are directly trying to classify, that is called "supervised". In this case it's not quite supervised, because their main evaluations are on the LFW dataset, which is a verification dataset, whereas their training on SFC is a recognition task. The difference is that in verification, you are given photos of two people you've never seen before and have to identify if they're the same or not. In recognition, you are given one or more photos of several people as training data, and asked to identify a new face as one of them. In theory, you could build recognition out of verification (verify all pairs between training images and test input images and assign the top-scored name as the person) but in practice it's much better to build dedicated recognition classifiers for each person.
Their main network is trained on a recognition task, using their SFC dataset. They show these recognition results in Table 1 and the middle column of Table 2. An error number of 8.74% (DF-4.4M), for example, means that they were able to successfully name the person in 91.26% of input images. However, this error rate crucially depends upon two key factors: (1) the number of people they're trying to distinguish between, and (2) the number of images they have per person. For this test, it was ~4,000 people, and ~1,000 images/persons, respectively.
If you were to add more people to the database, or have fewer images per person, this accuracy would drop. You can see this clearly in Table 1, where subsets DF-3.3M and DF-1.5M have correspondingly lower error rates because they have fewer people (3,000 and 1,500, resp). Similarly, the middle column of that table shows how error rates rise when you reduce the number of images per person.
In contrast, all subsequent results are shown on verification benchmarks (LFW and Youtube Faces). In large part, I suspect this is because of the realities of publishing in the academic face recognition literature: you have to evaluate on some dataset that the community is familiar with to get your paper accepted, and LFW is the de-facto standard these days, and it only does verification not recognition.
Here, their performance is certainly very good, and an improvement over previous work, but not an unexpectedly huge leap. If you look at the LFW results page, you can see that recent papers have been edging up to this number quite steadily: 95.17% (high-dim LBP), 96.33% (TL Joint Bayesian), 97.25% (this paper) http://vis-www.cs.umass.edu/lfw/results.html
Nevertheless, how are they able to get this boost in performance? What recent papers in this field have increasingly been discovering is that having higher-dimensional features can really give you a big boost, or to put it another way: having a higher-capacity model is what buys you the additional performance.
In machine learning, the "capacity" of a model refers (in a loose sense) to how powerful it is. The basic tradeoff is that a higher-capacity learner can more accurately classify testing data BUT it requires much more training data to learn. The problem is that for the LFW benchmark, the amount of direct training data you have is strictly limited: there are 6,000 pairs of faces, and you train on 90% of them and test on the remaining 10%. This is not nearly enough data to train a high-capacity model.
So what people have been doing is training the bulk of their models on some other data, for some other task, and then adapt that model to the LFW problem, using the LFW training data essentially to "tweak" the classification model for this particular task. That's why the LFW results tables are now broken up into different sections according to how much outside data was used and in what form.
In the case of DeepFace, this takes the form of the SFC dataset and learning a network for recognition, not verification. Since they have access to lots of data of this form, they can successfully train a high-capacity model for it. Then they simply "chop-off" the last layer of the network -- the one that does the final recognition task, and instead replace it with a component for verification using only LFW training data. Or for their "unsupervised" results, using no LFW training data ("unsupervised" in quotes because it's not really unsupervised).
BTW, this approach of training a deep network for some task, and then cutting off the last layer to apply it to a different task (in effect making it simply a feature-extraction method) is quite common, and has been applied successfully to many problems that might not have enough data to train a high-capacity model directly.
Anyway, if people have more questions, I can try and answer them. (I'm not one of the authors, but I am in the field.)