I have noticed that it can be hard to figure out how old a paper is from the paper itself. It is not that it is impossible: most of the time it can be found by a Google search. But why is there usually no publication data on the first page of a paper?
Here is an example: http://www.cs.toronto.edu/~fritz/absps/imagenet.pdf
One thing that may be causing the phenomenon that you are seeing is that in fields like computer science, authors are frequently allowed to put preprints online on their website, but not the final "official" version. Such preprints often do not carry a date stamp, while the official version available from the publisher's website does.
I would not agree that there is "usually" no date on the paper. Most published papers do carry a date. The one you link to was apparently published in 2012.
Manuscripts can of course come without a date, or even without an author. After all, nobody forces a manuscript author to date his work. (I guess that is the answer to your question.)
Style guides tell you how to cite an undated manuscript, typically as "Foo & Bar (n.d.)".
Many of the papers that you can find on the internet are what are called "preprints". A preprint is a manuscript prepared by the author (usually before the paper is submitted for publication, but it can sometimes also include corrections that were made during the review process, in which case it may be called a "postprint.")
When a paper is eventually published in a journal or conference proceedings volume, the publisher will often reformat the paper and typically add headers or footers to the pages that list the journal, volume, page numbers, etc. These headers/footers also typically include a copyright notice from the publisher. These published versions of papers are often unavailable to the public and can only be read by people who have personal or institutional subscriptions to the journal or conference proceedings.
Because of this problem of lack of access, many authors leave preprints up on their web sites so that anyone can read the paper. Thus you'll often find that a paper exists in a published version (with full citation information in the headers and footers) and a preprint version (usually without this information.)
The particular example that you linked to is a paper that was published in the NIPS 2012 conference proceedings. The published version is also available from the NIPS web site. Surprisingly, NIPS didn't format the paper with information about its being from the NIPS 2012 conference proceedings- this is a bit unusual in my experience but not unheard of.
