During the first Internet bubble^H^H^H^H^Hoom, the Internet Network Information Center (InterNIC) was turned into a private company, Network Solutions.
They were, for a time, the sole registrar for .com .net and .org domain names. Educational institutions used .edu, but I don't recall who was in charge of those registrations. For quite a while, it was $70 for two years, with no option of getting just one year for $35.
Looking at my whois record at arin.net and the company's IP range, it looks like we registered our .com in 1993. I can't find any confirmation emails, but I'm sure I paid by credit card.
Other domains were handled differently. Back in the early 90's, the .ca (Canada) domain was run by one guy based at the University of BC. To get a domain name, I sent him an email and asked for it. At the time, he enforced a consensus decision that .ca would be hierarchical: if you had a national company or organization, you could get a .ca If you were only in one province, say, BC, you could only get a .bc.ca name.