The problem
 The need for speed
Early games needed fast-moving screens full of action. One obvious way to do this is to simply have a framebuffer representing the image, and the CPU performs animation by updating the framebuffer. Early CPU-controlled games like Space Invaders did just that. However, you'll notice that games on that hardware typically didn't do much drawing per frame, and in Space Invaders when the whole armada is moving it's noticably sluggish. Simple math reveals why: these systems used 8-bit CPUs at typically 1 or 2 MHz. If you assume an average 320x240 resolution, even at Space Invaders' 1 bit per pixel, there are (320 * 240)/8 = 9600 bytes of RAM in the framebuffer to update. Assuming a highly idealized rate of updating 1 byte every 2 cycles, that means you need to be running at least 1.2 MHz just to update the screen at 60 frames per second. And that's not including AI, sound, and other game logic.
 Making it worse
This got worse when color was introduced: suddenly that 9600 bytes becomes 19200 bytes for 4 colors or 38400 bytes for 16 colors, with corresponding CPU requirements increasing to 2.3 and 4.6 MHz, which starts to be out of the reach of affordable early 80s microprocessors.
 The fix
 An unlikely source
The fix came from text-only display terminals. These devices split the screen up into rectangles of pixels formed from a fixed number of horizontal and vertical pixels, such as 7x9 or 8x8. In this way, the CPU can cause an instant change to all the pixels in a cell to a different letter pattern by changing a single byte in memory. Game hardware designers realized that if the "font" was changed to include the building blocks of pictures in addition to letters and numbers that this system would allow large-scale animation quickly at a low cost in CPU cycles.
Returning to our example of a 320x240 screen, tilemaps typically used 8x8 pixel cells (called "tiles"), so video RAM in this case would be only 1200 bytes. The same math as before reveals that you can change the entire screen at 60 frames per second in only 144,000 CPU cycles, or about 10% of a typical 1 MHz microprocessor. This is far more manageable. If you use 2 bytes per cell to get a far greater available graphical variety (65,536 pieces instead of 256), it's still only 20% of the CPU time.
Better still, increasing the color depth meant no change to the size of video memory or the amount of CPU required to update it. The CPU didn't need to care if each 8x8 tile was 2, 4, 16, or 256 colors. The video hardware obviously did, but it's the CPU we're most concerned about. And from the CPU's perspective this technique is a major work saver.
 The features
As electronics got better, tilemaps were given more effects. The first one was scrolling. A relatively easy change to the video hardware allows the CPU to control where in the tilemap the origin of drawing is, which means the screen can be made to move horizontally or vertically in any direction. The hardware will automatically loop around if it runs off the end of video memory, creating the illusion of an unbroken image. By combining this with making the video memory larger (typically twice the size of the screen) you can write in new data just off screen while scrolling so it appears that you have an infinitely long image that doesn't just repeat.
In order to give the programmers maximum flexibility, most tilemap hardware reserves one color (either a palette index or an actual RGB value) which is not drawn - it simply shows whatever was behind it. This allows you to stack tilemaps to create various fake perspective and other effects. It's also useful to increase the apparent color depth of an object. (Note that transparency is unrelated to the effect where you can see one object through another stained-glass style - that's properly called translucency).
Another easy thing to do in video hardware is to draw each tile mirrored: horizonally, vertically, or both. So by using a few bits in video memory for each tile as flip controls instead of just to pick an image you could achieve dramatic memory savings on symmetrical images. (This was also handy for flipping the screen in cocktail games).
 Color changes
By using a few more of the bits in video RAM as a color control for each tile it became possible to change what color palette a tile was drawn with. For instance, you could take text drawn in white and show it as grey, blue, red, green, or whatever without having the artist redraw it in all of those colors. This again allowed memory savings.
 Rotate and zoom
Around 1987 it was possible to pack enough circuitry into a small custom chip that arcade manufacturers started adding rotate and zoom capability (commonly abbreviated as "ROZ", and probably best known to many gamers as "Mode 7", after the display mode on the Super Nintendo that featured it). Namco was first out with the effect (in games like "Assault"), followed by Konami and others. This was probably most commonly used to provide a perspective ground or road, but it was also usable for many other effects.