Bit of a history lesson... I'll give you some ideas of how this would have worked in general.
Bear in mind that in those years there weren't really canonical ways of developing games - it tended to be a one or two person endeavour that depended entirely on the ingenuity of the programmers involved. They didn't have access to the internet or, typically, to academic texts. You had the manual / specification for your language of choice (often C or Basic); that was about it.
Some approaches, like RLE for byte or bit-level compression (for secondary storage), were certainly more common. More complex algorithms like ZIP, were still years away.
Binary-level data: nibbles
The idea here is that you can use less than a single byte, to store some element of data. A fraction of a byte was historically termed a nibble. One used to hear this term used often, since it was crucial to use every last bit of your 16-128kb (typically) of memory.
For example, for a typical roguelike, which in the present day would typically use 1 whole byte or 4 byte word for each map cell, a game constructing a similar map then might have used 1-4 bits for a wall. If all you have is one type of wall + empty space, then 1 bit per wall suffices; but if you needed 8 different types of wall, you'd use 3 bits (2 to the power of 3). So 0 might be empty space, 1 a stone wall, 2 a wooden wall, etc.
If you need to store multiple dimensions of data, for example if a wall has up to 4 hit points, then you would need an additional 2 bits to represent those 4 values.
For the sake of ease and reduced instructions to decode this data (remember, < 2Mhz was not uncommon at the time), the nibbles would usually be a power of two: 2^0 = 1 bit nibble, 2^1 = 2 bit nibble, 2^2 = 4 bit nibble.
The reason for this is the way CPUs access data on byte (now word) boundaries. For example, for 5 bit nibbles, two in a row would anyway take up 2 bytes (10 bits and then another 6 unused or part of the next nibble), but sit at different offsets, meaning you have to do that much more (conditional) processing just to get at your 2nd element's data - even today, this is not worthwhile. At that time, it would have been a waste of a very limited resource - processor cycles.
Primitive compression: RLE
The idea here is that the more large, solid or empty, contiguous spaces you have, the better compression you will get. Instead of looking at some fruit and going, "Apple, Apple, Pear, Banana, Banana, Orange", you say 2A1P2B1O. The more apples and bananas next to each other, the better the compression.
When bringing data in from the disk for each new level, RLE or other primitive forms of compression were used. But for in-memory data,aAt 320x160 full screen resolution, a full screen of 8x8 tiles = 40x20 = 800 tiles. 800 x 4 bits = 3.2bk - already a considerable amount for the time. Depending on the characteristics of that part of the map, you might compress down to 30%, so 1kb in a good case.
This was why games of the open world type tended to have far fewer terrain details than they do today: examples include BattleZone and Koronis Rift. The Eidolon and Rescue on Fractalus stored a jaw-dropping amount of terrain detail for their time, using heightmaps similar to more modern voxel engines such as that in the Novalogic games like Comanche, or even Minecraft.
Sparse data structures
The idea here is that empty space need not be specified: only things that exist are specified with a position in otherwise empty space.
The Apshai series by Epyx used exclusively (screen) axis-aligned, rectangular rooms, so for this sort of level description, you can expect much better compression than for cell-based maps, as all you need store is the x, y, width and height of a limited number of rooms. Width and height could even be specified in 4-bit nibbles as 1 single byte, giving you just 3 bytes per room! (excluding monsters and treasures). These values could then further be subjected to bit-level compression.
This an example of sparse data specification, which comes in many forms, specifying just the centre position and radii of circles or spheres for example, which is how 1990's game Ecstatica specified its 3D geometry to its renderer.
Note that sparse data can also be used as an intermediate format, which is then expanded before the level begins. Perhaps we need map cells / tiles to walk on; that is what the sparse data will then be expanded to, so that the player can move around. The moment the level completes, this expanded data is discarded and only the sparse data remains (in memory or, more likely, in secondary storage).
Today's sparse data structures include octrees and point clouds.
Generation at runtime from minimal "seed" data
This is what we today call procedural generation. Various mathematical, bitwise and logical operations are used to expand a relatively small series of bits into vast quantities (in some modern games, enough to form an entire galaxy of detailed systems and planets) of data. Or in the original Rogue and its follow-ups, enough data to create countless fairly sized, well detailed maps of terrain, creatures, traps, vaults, treasures etc. The only limitation was how much "map" the machine could hold in memory at one time, once generated just before entering a level.
Probably the seminal release was Rogue (1980), which offered the player multi-screen maps on your typical 80x40 ASCII terminal display of the time. ProcGen took 8-bit architectures to the limit with David Braben's Elite, which was ported to many 8- and 16-bit platforms, due to its success.
The main issue with this approach is that it is hard to control exactly what it creates, so programmers have to give up a degree of control in order to gain an endless variety of possible levels without the need to actually store them - instead being generated at runtime, just before the level commences. There was a fascinating article on the web a few years ago, where David outlined the many complex hoops that had to be jumped through in code to "reign in" and amend the original, procedurally-generated world (one of millions that they could have chosen, mind you) to the relatively sensible galaxy that Elite eventually shipped with.
And as with the other approaches, you can only expand as much into data as you have space for, which in those days was limited indeed. So this limits the amount of data you the player can read before some more loading/expansion takes place.