In the second half of the 80's we generally still did not distribute papers electronically and the world wide web remained several years away. Nearly everyone in theory subscribed the the Theorynet mailing list (not so true today) and the call for papers were emailed to this list as well as sent out to all SIGACT members by postal mail. To submit to a conference we had to make ten copies of a paper and physically send them to the program committee chair who then sorted the papers into ten stacks and sent each stack to each program committee members. A few months later the program committee would meet and choose the papers for the conference sending out accept/reject letters through postal mail. Since MIT always had one or more PC members on the faculty we found out about our papers from them well before we got the official word.
Initially the STOC and FOCS PCs did not take deadlines seriously. For some reason about 1987 they decided to strictly enforce the deadline first by postmark and then by receipt. Federal Express made considerable money from us theorists and I can still tell you which Fed Ex offices in Boston and Chicago remained open the latest. One year an MIT faculty memeber hired a same-day service to send the papers to the PC chair giving us at MIT an extra night to work on our papers. Not many of us showed up for classes the next day.
Electronic submissions, starting in the early 90's, leveled the playing field and made the process slightly more sane. The STOC call still has the line
Authors who cannot submit electronically must send 21 printed copies (double-sided preferred) of an extended abstract, together with a cover letter, to:When I served as the Complexity PC chair in 1999 exactly one person sent me their submission by Federal Express. "Am I going to have to send a copy of this paper to each of my PC members?" I thought. Instead I emailed the author and luckily he sent me a postscript file and I could manage the PC electronically. We have since removed the non-electronic submission instructions from the Complexity call.