How did researchers find articles before the Internet and the computer era?
We depended on libraries and librarians. Grad students would spend hours in, say, the math section of a good academic library, going from book to book and taking copious notes (on paper, of course).
But, often enough, the next paper we needed to look at wasn't in that library at all, so you would go to the librarian and ask for a loan of the resource from another library.
But it was also an important technique to use the librarian as a 'knowledge expert' who could, and would, suggest things for you to look at and places to look. I don't know if librarians still get the training to do that.
And, of course, you could ask your colleagues for hints about which rocks to uncover to find the gems.
One point that the other answers have passed over is that there were various services the libraries subscribed to which surveyed the literature and provided abstracts and cross indexing of the primary journals. Science Citation Index was mentioned in a comment, but there was also Science Abstracts, which had been published since 1898. These were hefty print volumes, and consumed a significant fraction of the library's shelf space and budget.
You'd typically start with a paper your mentor pointed you to, use the Science Citation Index to see who had cited that paper, then look up those papers in Science Abstracts, march off to the shelves to find the appropriate bound copies of the journals, and then plug nickels into the copy machine. If your institution didn't have that journal, well, that was what the interlibrary loan was for.
(Comment extended to post:)
My impression is that part of the answer is "they didn't", or more precisely "they were only as good at it as their own knowledge and that of their communities". In particular, at least anecdotally, many things in mathematics were discovered in parallel for lack of easy communication and inter-visibility. [This is complementary to @Buffy's answer, which explains why people found anything at all.]
I have tried to put this on solid footing by comparing numbers of references in a 1970 issue of a mathematical journal vs. in a 2019 issue of the same journal. This turned out to be surprisingly nontrivial. Firstly, it's not clear if I am comparing apples to apples, since most journals have changed their publication criteria and sometimes even their (implicit) subject within these 49 years. Secondly, papers in almost every part of mathematics have gotten much longer (by a factor of 2.8 in my sample). Thirdly, empirically, Project Euclid bans your IP if you load more than about 20 PDFs in rapid succession, and Sci-Hub is slow and has captchas. There might be a way to do such research using MathSciNet, but I am nowhere near proficient enough at its use.
So I ended up comparing Proceedings of the AMS (due to their long back-catalog of freely accessible issues), and came up with this ("reference" means "bibliography item", not "place where a bibliography item is being cited"):
I picked 13 of the papers from Proc. AMS 141 (2019) #12 (more or less picking the first 13, except I skipped a few from the Abhyankar cluster since he writes and cites in rather idiosyncratic ways). The average paper has 1.5 references per page:
I picked 13 of the papers from Proc. AMS 24 (1970) #1. The average paper has 1.2 references per page:
Should we really compare references per page? There are good reasons to assume that the number of references per page should decrease as papers get longer, since the references cited in Section 1 won't normally be disjoint from the references cited in Section 2. As a consequence, the discrepancy between the above numbers looks even starker.
I can only explain this discrepancy in two ways:
the literature has grown much larger, and not just by the addition of new disciplines but also by more people writing about the same discipline;
(as the OP observed) finding relevant references in the literature has gotten easier thanks to the Internet, Google Scholar, etc.
I don't know how to properly disentangle these two causes.