I just barely spanned both styles in my researching career. In some ways, it’s the same, but to the extent that it’s different, let me say that I like the modern computerized systems much better.
The simplest method was to take a guess at what journal an article of interest would be in, and in what date range. Most journals maintain an index which they publish every decade or so. You obtain the index for your decade, and look up various key terms in it. Each of those will lead you to a list of specific references, and you then obtain those, and read through them and decide which are relevant and useful. Note that “obtain the index” and “obtain the journal papers” might, in some cases, entail filling out a form for each volume you needed, and handing it to a library employee who would then delve into the restricted stacks and bring you back one volume at a time, for you to not take out of the library.
Once you had a few papers which were at least somewhat relevant, the next step would be to look through the reference lists in those papers, for papers they cited. Some of those might be of interest to you, too. You could then check those papers (which might require more forms for the library employees). It was also possible to check for papers which cited a paper you already knew of, but the databases for that were often incomplete, and in the pre-computerized versions, more cumbersome to use. Both of these methods are still important for research, though (especially for forward-referencing) they’re now much easier.
To leverage the afore-mentioned method, you might start your search with a “review journal”. Most fields have one or two of these. The papers in a review journal don’t represent new contributions to knowledge, but rather compilations of others’ contributions. So the reference list for a review article will generally include the most important papers on a subject. Again, these still exist and are useful.
And finally, then and now, a lot of paper-finding was done by word-of-mouth. This is, in fact, one of the main reasons that most research is done at universities and other institutions, rather than by independent individuals: You can talk with colleagues, and ask “Are you familiar with any work done in this field?”, or “Did you hear about the new technique that the group over at University X is using?”, or “How do these results relate to the work of So-and-so et al?”. You can also encounter ideas from visiting faculty, or guest colloquium speakers, or at conferences, or the like. This was and is perhaps the most important way of finding information, and even this is easier with the Internet, thanks to e-mail and other methods of communication.