Line Scrolling (Air Zonk):
Notice how all the layers seem to be "cut"?
It's just changing the speed of the background right before the next line is drawn via interrupts, and this is done a number of times during a frame.
Shoving sprites in smart positions (Darius):
Notice how the foreground has a lot of "empty" space? They abused the fact that you can't have anything going over those mountains and just use sprites there, since that way the sprite limit per line won't be reached.
It was also used in reverse on adventure island, where they are used as the background (also leaving a lot of empty space).
Requires careful planning.
Dynamic Tiles (Star Parodia):
The background is drawn as a series of tiles (8x8 blocks).
Those tiles can be animated.
As the map is moving (say... 2 pixels to the left per frame), these games animate some tiles in the background, drawing them as if it moved 1 pixel to the right.
The result is that a section of the background appears to be moving SLOWER than the rest of the background and, as such, seems like a separate and further away layer.
This takes a lot more memory and is quite limited (tiles have to be placed always next to the same tiles), but looks really good and doesn't waste sprites nor is it limited to "cuts".
Some games also use the cut trick to move parts of the map vertically, making it seem like they're overlapping other parts of the map.
Gate and Lords of Thunder use ALL of these tricks, really amazing stuff.
There's also my super awesome palette animation trick, but all that nets you is an Amiga style single color background like in Shadow of the Beast 2.