Shipping as a fannish phenomenon definitely predates the internet!
Many aspects of fandom today have their roots in pre-internet Star Trek fandom - specifically, the women who loved Kirk and Spock and wrote/disseminated fanfiction about them.
These early shippers generally communicated by mail and at conventions, and shared their fanfiction in photocopied zines. Initially, they would have met up at general science fiction conventions throughout the year: Boston's Boskone, New York's LunaCon, and others along the east coast, with smaller ones in between and the global Worldcon held in September. In the 1970s, there were Star Trek-specific cons that dwarfed the attendance rates of the general, more literary ones, and while those calmed down by the end of the decade, Star Trek fans continued to organize smaller cons on their own, sometimes arranged around specific zines or type of fic. All of this would be, again, publicized through the mail, at other conventions, and by word of mouth.
The general cons that focused on hard science fiction and more literary works were extremely male spaces, but once cons started focusing on specific mainstream media properties, it became clear that women were just as into fandom as men - and while many fannish spaces were still quite hostile to women, rooms and communities centered around producing fannish media (fanfic and fanart) tended to skew female. And this fic and art could be very romantic and/or sexual. Star Trek fandom invented the "Mary Sue" (a super-talented original female character), the self-insert (called a "lay story", where an original female character, typically considered a Mary Sue, sleeps with one of the major canon characters), and slash (so called because the romantic pairing of Kirk and Spock was indicated with a / between their names, now a very common way of indicating a romantic pairing. Kirk/Spock as a specific pairing was often referred to by fans and detractors as "the premise").
In writing these stories, fans adapted certain incidents from Star Trek canon into tropes that would go on to be common across fandom. In the episode "Amok Time", for instance, the Star Trek writers created pon farr, the time when Vulcans would have to mate or die, which was certainly made use of in Kirk/Spock fic, and would be translated into similar issues for human characters in other stories. (You can see the end result in modern omegaverse worldbuilding.) Likewise, the episode "This Side of Paradise" involved an alien pollen that lowered inhibitions, which was further used in fanfiction as an excuse for characters not yet at that point in their relationship to have sex. Aliens sometimes mind-controlled the characters on the show, which likewise was used in fic to create sexual situations, a trope now called simply "Aliens Made Them Do It". And in multiple episodes, characters were taken captive or enslaved, resulting in similar situations in fic - whether as a new episode in the established canon or in alternate universes where Kirk and Spock were not captain and first officer.
Other trends were a bit more generic. It was very common for K/S fic to focus on the two having repressed feelings for each other and finally admitting it, just as fiction about heterosexual relationships has for centuries. Domestic-focused fic set years or decades into a settled relationship between the two were also popular.
Some other fandoms relevant to pre-internet shipping are Blake's 7, Starsky and Hutch, and Highlander. The Star Trek fandom actually helped to popularize Blake's 7 after it began to be shown on American television in the late 1980s, and also changed its fandom dynamic - where early Blake's 7 fic focused dramatically on the relationships between the leads and used themes of psychological manipulation, the influx of Star Trek fans brought a more romantic/sexual vibe. That is, people who were originally attached to a specific pairing had become "shippers" who were attracted to ship potential in a more general sense. It's a big thing!
However, the term "shipping" itself is an invention of internet fandom, originating in X-Files fandom on Usenet: those who thought Agents Mulder and Scully should get together in the show were MSR (Mulder Scully Romance) fans or "relationshippers". It would eventually become shortened to "shippers" and become more generalized.
My major source here was the ethnographic work, Enterprising Women: Television Fandom and the Creation of Popular Myth, by Camille Bacon-Smith (1992). The panfandom wiki, FanLore, also has a very detailed discussion of shipping culture in Star Trek fandom, with selections from and links to primary sources.
Oh my dear sweet summer child.
Before "shipping" there was "slash fiction", so-named because such fiction would concentrate on an unlikely romantic relationship between characters (X/Y). I believe the origin of the term goes back to Kirk/Spock slash fiction related to the original Star Trek TV show from the late 1960s.
Slash fiction took off in the 1970s, with Star Trek and other various popular media franchises as source material (such as Starsky and Hutch). The majority of erotic slash fiction in the early days of the '70s was written by women (who were the core of the active fandom for many franchises back then) and focused on male/male homoerotic relationships. Stories were typically circulated only in small groups through zines or newsletters (in physical form, of course, until the advent of BBSes and other forms of online community in the late '70s and after). Though some stories ended up being published to a wider audience. And this also had some overlap with and influence of mainstream fiction writing, as you can see an uptick in male/male erotic sf/f genre fiction writing at the time. And a substantial amount of these works ended up in the hands of others outside these communities, as, say, gay men who weren't necessarily star trek fans read works of Kirk/Spock slash fiction written by women. For example, Diane Marchant's "A Fragment Out of Time" is the first published work of Star Trek fan fiction, from 1974 and is an example of Kirk/Spock slash fiction.
Many of the common tropes of the sub-genre were established very early on, such as the idea of the "one true pairing" or "OTP" (the "ship") and, of course, the non-heterosexual romances between characters that are not necessarily explicitly romantically involved within the traditional "canon" of the media. These highly active communities of slash fiction writers formed a substantial part of the early fanbase for many of these media franchises, including Star Trek, and did a not inconsiderable amount of work in keeping the fandoms alive after the shows ended through fanzines and conventions (which would blossom in popularity through more mainstream audiences through the '70s and afterward due to the existence of those conventions in particular). And they maintained communities that morphed and adapted through different eras of technology through the usenet, BBS, and email eras to the web and all of the modern highly popular fan fiction sites today (which currently have millions of users).
Arguably fan fiction itself is as old as storytelling and literature. The Illiad and Odyssey could be argued to be types of fan fiction, as could The Aeneid by Virgil, Dante's Divine Comedy, Milton's Paradise Lost, The Three Musketeers by Dumas, and so much more. The view of fan fiction as an explicitly modern concept throws some light onto the changing relationship of society to shared mythologies and to storytelling in general, especially with the rise in commercialized entertainment in the past few centuries. We generally wouldn't think about, say, the "Arthurian Literary Universe" in those terms, for example. Part of that has to do simply with age, but part of it has to do with the changing relationship of commerce to storytelling and especially the rise of explicit ownership over mythologies and fictional works through copyright and trademark law. Which itself has become strengthened and formalized due to the profitability of commercialized storytelling in the industrial age. That's a big part of what makes fan fiction feel more modern, and it's interesting to consider that aspect in relation to the differences in the cultural perception of the legitimacy, seriousness, and sophistication of works of fan fiction versus older works that have a similar relationship to their settings.
The particular genre/trope of injecting explicitly romantic same sex relationships into popular fictional settings seems to be a more modern invention though, at least to the level of popularity that exists today. The '60s and '70s were an era of loosening of social mores and greater acceptance of open homosexuality. That's reflected not only in the rise of slash fiction in the '70s but also in a new wave of gay or queer literature around the same time (such as Baldwin's "Another Country" from 1962, Vidal's "Myra Breckenridge" in 1968, Pynchon's "Gravity's Rainbow" in 1973, and "Kiss of the Spider Woman" by Puig in 1978) and the rise of "yaoi" (depictions of "boy love" romance in manga for women) in Japan, also in the '70s.
Edit: some suggestions for people wanting to learn more about this stuff: