First on the issue of image sizes: Less 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 less colors, less information required for the positioning and values of each pixel.
But certainly there were more tricks involved.
The NES (Nintendo Entertainment System) split an image up into tiles and blocks. 4 8×8 tiles made one 16×16 block, which also means that your image could be done as hexadecimal values. Every memory page contained 256 tiles of 2-bit raw pixel art, but you could repeat it in various locations to save on memory. For example, by having 90% of the sky simply the same blue. Or by having NO background at all (this is also why ‘black’ was often a bit different from TV to TV). Or at least by repeating certain tiles quite a bit; like in the floor or walls.
The NES had 64 palettes. Every palette was a selection of 3 colors plus the shared background. A single palette could be used PER block. So each tile was now just a memory page location and an allowed palette. So the image only needed to call on the 2-bit memory location of each tile, and the 2-bit palette selection of each block. And guess what? The NES? It had 2 nametables, allowing the side-by-side or top-down screen systems in so many games; this is what allowed for the illusion of scrolling, when in fact only what was on screen at the moment ‘existed’.
Then things get even trickier. Some games would exploit the flickering or the 60hz refresh rate. Recca, for example, is famous for making everything exist only one out of two frames, allowing them to clutter the screen with even more explosions and enemies with two alternating 30fps images ‘superimposed’ as far as our eyes can tell. Sprites had their own additional memory page, and were used for anything that isn’t in the background: Megaman’s life-bar was a sprite, while your hearts and bombs remaining were in the background in LoZ. Sprites had their own locations on the screen independent of the background, which was great for the life-bar as you moved, though.
An individual sprite had to be 8×8, but the result was that they made most characters into multiple sprites. This limited many games though, because there was a limit of 8 per horizontal line. Anything over that limit would not be rendered, which was going to be problematic when you already had 2 or 3 per line all making the main character. This was the source of much flickering; once player actions were taken into account there was little the developers could do sometimes.
There was also the other hardware to take advantage of: The TV! By doing loops or timeouts on certain parts of the graphics, you could take advantage of the tv’s vertical blank (these become blatant sometimes once emulated on newer screens) to refresh the picture unit, to change the timing or loop certain cells, which could allow animation or certain effects on the cheap RAM-wise, although those instructions required quite a bit of knowhow 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.
Pretty much every game had its tricks; those are just the very basics and a small handful.