Some dictionaries source attestation and try to go for the earliest quotes they can find. How do they find them? Without electronic indexing this must have been impossibly difficult.
The reason I'm asking is that many answers on Stack Exchange often conclude earliest attestation and imply earliest use, instead of the logical used at the latest in ... That's a slightly different issue to frame the question, not to make it too broad. To be fair, no inference is made because of this in many cases.
I agree with your assumption that the date of the earliest recorded usage of a word does not necessarily correspond to the earliest usage of a word, since words may have been in circulation in spoken language before they were first used in publications, and many old publications have simply not survived. I touched upon this issue in my answer to the question How many of Shakespeare's words in his plays were new? on Literature Stack Exchange: a number of words that are first attested in Shakespeare's plays may have circulated earlier, either in the spoken language or in writings that have not survived (or both).
Before there were digital corpora and digital texts, lexicographers had to read physical books to find usage examples. The editors of the first edition of the Oxford English Dictionary (which started their work in 1857 or 1858) asked thousands of volunteer readers to submit usage examples, in what was an early example of crowdsourcing. (See the crowdsourcing timeline, which says that 800 volunteers contributed to the first fascicle alone.)
See also the description of the OED's Reading Programme. James A. H. Murray set this up in 1879; its focus was not specifically on finding the earliest examples of words and phrases. In addition, the first edition "relied heavily on a small number of authors (notably, of course, Shakespeare) for its coverage of Early Modern English (1500-1700)". This selection was possibly too narrow to find the earliest surviving examples of words and phrases. For this reason, the current Historical Reading Programme looks at a broader spectrum of texts:
Today, readers systematically survey a much broader spectrum of texts from this and other periods. A separate Historical Reading Programme has been created to serve this function. Readers participating in this programme supply material specifically for the revision of the OED; usually these are earlier examples of words or phrases that are already included in the Dictionary. These readers check their findings against the Oxford English Dictionary to ensure that only significant items are filed, such as earlier examples of words and meanings or terms that have not yet been registered in the database.
In short, before the digital era, finding early usage examples required a lot of reading.
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.
See also:
It is not uncommon to detect word usage that predates the earliest attestation noted in the OED, for example in the Corpus of Early English Correspondence such earlier attestations were found.
Of course, when really every written document from the past is digitised this process comes to an end unless some old writings are newly discovered.
