Thus, the paper is about using an unsupervised system to help a later supervised system. An advantage of this is that, as the unsupervised system isn't trained to recognise object X, it instead learns features that are discriminative. This same network could be used to recognise arbitrary objects (which is what they do later on in the paper with ImageNet).
What he's trying to talk about is "this is an unsupervised feature detector in a large dataset which is only categorized, and where no human has provided correct answers up front to verify progress."
The reason this matters (and it doesn't matter very much) is that that means that in cases where it's prohibitive to provide training sets, such as where you don't know the good answer yourself, or where giving a decent range of good answers would be difficult, this sort of approach can still be used.
"isn't that basically equivalent to labeling them?"
Yes. It is. The original poster is confused.
What he meant to say was "there is no training set."
I apologize for being vague, and shall endeavor to be clearer in the future.