A friend of mine, a modern-languages teacher, was marking exams in the pre-internet days and thought he recognised a passage in one, so looked it up in several text-books and discovered that it had been plagiarized from a text-book that he himself had written.

This is not just an (amusing) anecdote. One very important way in which plagiarism was detected was by familiarity with the regular books.

The same ways one detects plagiarism now really - through similarity to other pieces of writing and/or how different it is from the student's normal writing or work. If you have seen someone's work before, or even within the same document, people will have their own writing styles - using particular phrases often for example. When that suddenly changes, it's a bit of a red flag.

Things like Turnitin aren't a panacea that solves the problem, they're quite blunt objects at detecting plagiarism. For example, that program will pick up anything quoted as something of concern, even though when looking at the paper it's properly cited and acknowledged as someone else's work.

History prof here, old enough to have taught college students before the web (though not the net itself). The fundamental change to keep in mind is that prior to the web taking over information delivery-- which really means >2000 or so --college students generally didn't have access to source material outside their own campus libraries. While there were "online" linked databases in the 1980s (Lexis and Nexis both went national c. 1980, Westlaw terminals were common in law libraries in the late 1970s) these were usually "pay by search" so undergraduates didn't usually have unrestricted access and they weren't full text anyway. Researchers had to find sources using published bibliographies or other hard-copy tools, most of which would lead to materials not actually held by their campus library collections (unless said student was at a major research university). Moreover, interlibrary loan was done via photocopy/mail, so it often took several weeks to get a copy of an article that wasn't in the library.

Consequently, it wasn't that hard for an instructor to have a pretty good sense of what materials were available to students on her/his campus, especially if the same assignment (say a research paper on a fixed topic) was given year after year. When reading such papers in volume (in grad school I read 150-200 papers on the same assigned topic more than once) you quickly realize there are only a handful of logical answers to be formed from the limited sources available; any major deviations, amazing insights, or unique sources would immediately draw attention and likely lead to more careful review, under which it is fairly easy to "catch" a student who is deviating from her/his own voice...from there's it's simply a matter of figuring out what the source material was. In many cases-- and this is still true at my liberal arts college --the faculty who were assigning and grading these assignments were also the people responsible for building the library collection in that field, so they might well have personally selected many of the books students were using in their research (the obvious exceptions being large research universities with field librarians and multiple faculty in the same subfields).

Because access to source material was more limited before libraries went fully online, it was easier for faculty to know what material students read while writing their papers. If you go back far enough, there was also simply less material period in many fields. For example, in my field-- environmental history --it was relatively easy for historians to read every journal article and potentially even all the monographs published in the field well into the 1990s. In fact, there was a sort of tradition of publishing "review of the field" articles that did just that, reviewed all the scholarship in the field, up until the early 1990s...I recall one in Environmental History Review in that period in which the author (William Cronon?) basically said "This is probably the last time anyone will be able to say they have 'read all the new scholarship' in the field because the pace of publication has increased so rapidly in recent years." Publishing in all fields has proliferated over the last 30+ years to a remarkable extent; since ~2000 students have not only had access to full-text journals and things like e-books, but also less formally published materials like blogs, all of which are ripe for plagiarism. Prior to that it would have taken more work for an average student to travel to a specialized library and find a source like The Journal of the Lewis and Clark Trail Heritage Foundation to plagiarize than to simply write the paper legitimately.