What is it?
Tower Defense maps are a popular breed of user-created maps primarily for StarCraft and Warcraft III. While every map is different, the main idea is to kill off waves of enemies before they can reach their destination. Most enemies do not attack on these maps- the point is not to build a defense that can withstand attack, but one to impede movement.
How do you play?
Making mazes out of towers and walls is a popular way to impede the enemy; other players exploit the system by using the popular "boxing" tactic, in which they form a box with one open end facing the direction the enemies eventually want to go. This can only be done on intersections. The idea is to make the enemy circle the outside of the box, retrace the path back to the intersection that was blocked by the wall of towers, and then retrace the path yet again to move towards their next waypoint.
Every enemy killed usually gives you resources with which to build more defenses. In addition, most maps give a fixed or scalable amount of resources at the beginning or end of every wave. Some even give you interest on any resources you have saved up.
What if enemies DO get past your defense?
Most maps work on a "lives" system: You may only let X number of enemies "leak" through your defenses. The lives may be for individuals, or shared by a team. Other maps have no lives: if you let even one enemy slip past, it's game over. Maps with no lives, almost without exception, only eliminate single players at a time, for obvious reasons- if a newbie joins an 8-person game and messes up, only he should be eliminated. (Most "lives" maps compensate for this possibility by layering the defenses- i.e., multiple people deal with the same wave of enemies.)
One may wonder, "Why not simply build a wall that the enemies can't pass at all?" The answer lies in the programming of the enemies: if they are completely blocked, they will switch from a "move" action to an "idle" action which will cause them to attack any enemy that is within range. They will not be content with blowing a small hole in the wall at this point: they will continue pounding it until either they or the wall is completely annihilated.
Origins:
The debatable precursor to the modern Tower Defense map is the famous Lurker Defense map for StarCraft: Brood War. A slew of clones were soon made, and the idea was immediately used in Warcraft III when it hit shelves.