They were free, and only took a letter (not email...) to the internic. I remember when we registered Autodesk.com, not much impact at the time because we didn't have a connection to the 'net yet. My email was still {gatech,uunet,MIT}!acad!eric.
I registered one via a phone call in 1994. It was just one guy doing them all.
I'm going to guess expensive and full of paperwork.
Expensive? Domains were free up until at least 1995.