Fewer pixels means less data right from the start. Say you’ve got a 256×240 image. Compare to how many pixels you’ll have on a 1920×1080 screen! Additionally, there were fewer colors, less information required for the positioning and values of each pixel. But certainly, there were more tricks involved.
The Nintendo Entertainment System divided an image up into tiles and blocks. Four sets of 8×8 tiles made one 16×16 block, which also means that your image could be done as hexadecimal values. Each memory page consisted of 256 tiles of 2-bit raw pixel art. However, you could repeat it in various locations to save memory.
For instance, you could create 90% of the sky simply blue. Or by having no background at all (this is also the reason why ‘black’ was often a bit different from different televisions to televisions). Or at least by repeating certain tiles quite a bit, like on the walls or the floor.
The NES utilized 64 palettes only, and every palette was a selection of 3 colors and a shared background. One out of 64 palettes could be used per block. Therefore, each tile was now nothing but a memory page location and an allowed palette. The image only needed to call the 2-bit memory location of each tile through code, along with the 2-bit palette selection of each block. And interestingly, it had two name tables, which allowed the side-by-side or top-down screen systems in so many games. Therefore, this is what allowed for the illusion of scrolling, when in fact, only what was on screen at the moment ‘existed.’
Then things got even complicated and trickier. Some games would utilize the flickering or the 60Hz refresh rate. For example, Recca is quite famous for making everything appear only once in two frames, which allows them to clutter the screen with more explosions and enemies, along with two alternating 30 frames per second images, superimposed.
Sprites had their own additional memory page, and were used for anything that isn’t in the background: Mega Man’s life bar was a sprite, while your hearts and bombs were in the background in LoZ. Sprites had their locations on the screen independent of the background, which was great for the life bar as you moved.
A single sprite had to be eight by eight, but the result was that they created most characters into various sprites. This step put a restriction on many games, though, because there was a limit of eight sprites on each horizontal line. Anything above that limit would not be rendered, which was a big problem when you already had 2 or 3 per line, all building the main character. This also produced much flickering; once player actions were taken into account, there was almost little the developers could sometimes do.
They also took advantage of the hardware of the TV! By putting together loops or timeouts on certain parts of the graphics, you could take advantage of the TV’s vertical blank to refresh the picture unit. It was to change the timing or loop certain cells, which could allow animation or certain effects on the cheap RAM-wise. However, those instructions required quite a bit of know-how and timing to look good. Combined with bank-switching (the art of just reassigning the image to a new position in memory), you could make stuff like waterfalls or ‘moving-relatively-to-the-camera’ backgrounds.
Almost every game, including Super Mario, had its tricks back then in the old times. The things we mentioned above are just the very basics.