Typically, you don't ever really know for certain that you have the earliest example. Or even the earliest written example. It's just the best so far.
(As a person who frequently writes answers to etymology questions on ELU, I try to make this clear. "According to the OED", "according to my own research", "dates at least back to X" are all things I say, but I sometimes get sloppy and don't do this all the time.)
There are some exceptions. We can be very certain that "cromulent", for example, was coined in 1996 (or '95 depending on when the episode of the Simpsons was written).
How etymological research is done has varied through time. In the case of the "New English Dictionary" (the first edition of the Oxford English Dictionary), work started on it in 1857. Then:
[I]n January 1859, the Society issued their 'Proposal for the publication of a New English Dictionary,' in which the characteristics of the proposed work were explained, and an appeal made to the English and American public to assist in collecting the raw materials for the work, these materials consisting of quotations illustrating the use of English words by all writers of all ages and in all senses, each quotation being made on a uniform plan on a half-sheet of notepaper, that they might in due course be arranged and classified alphabetically and by meanings. This Appeal met with a generous response: some hundreds of volunteers began to read books, make quotations, and send in their slips to 'sub-editors,' who volunteered each to take charge of a letter or part of one, and by whom the slips were in tum further arranged, classified, and to some extent used as the basis of definitions and skeleton schemes of the meanings of words in preparation for the Dictionary.
An Appeal to the English-Speaking and English-Reading Public to Read Books and Make Extracts for The Philological Society's New English Dictionary
The "Reading Programme" is still used by the OED, although the methodology is different. The books are still read all the same but here's what happens next according to a freelance researcher for the OED:
I then consult OED Online to determine whether the word or phrase is in the Dictionary: if it is not, I submit it as a ‘not-in’, and if it is, I decide whether its form or context is important enough to warrant its submission. If it does qualify, I enter the information into tagged fields in an electronic file that has been set up in a standard format. When I have finished the reading, I submit the file to Oxford or New York, where the records are incorporated into OED‘s working database for consideration by the editors, along with thousands of paper citation slips, as they proceed through the current revision. Yes, some of my finds are still submitted as paper slips—a reminder of OED‘s long heritage—but, electronic or paper, I can hardly imagine a better job.
The quotations were collected in a machine readable format for the first time in 1989. The 1990 UK Reading Programme captured material electronically. (Note that the second edition of the Oxford English Dictionary came out in 1989.)
In addition to this, the OED now utilizes several online databases of texts, such as Early English Books Online, Eighteenth Century Collections Online, and some newspaper databases.
If you do your own research with databases (many people use the free Google Books), it's often easy to find antedatings for pages that haven't been updated for the third edition of the OED. Updates to the OED3 started in 2000 and continue to this day: it's a huge dictionary and updating takes time.