What is it?
I first noticed Lurker Defense maps, user-created maps for StarCraft: Brood War, on battle.net in late '00. As the popularity of the concept exploded soon afterwards, it's safe to assume that they did indeed originate at that point in time. The basic premise is to kill all enemies (who attack in a series of waves) before they can reach their destination.
How do you play?
The classic Lurker Defense map only had lurkers. You were to burrow them in formations that would allow for quick and efficient killing. The most popular formation- at least, one that I used extensively, to great effect- was a V-shape, with the point facing away from the advancing enemies. Other formations may have worked better. Straight lines that were perpendicular to the enemies' path were ineffective, though in rare cases a straight line that followed the enemies' path could work well. The enemies would have to be in a perfectly straight line, however.
In the classic variant, enemies would attack any of your lurkers that they could see. This discouraged you from unburrowing your lurkers unnecessarily, though you could rearrange your formations if necessary between waves.
Other varients allowed you to use non-lurker units to funnel enemies into your defense in the most advantageous way possible. In these versions, enemies would rarely attack- they would just move innocently towards their destination, not caring when they were hit. When blocked, however, they would get nasty and attack.
Additional lurkers were usually given to you at the end of each wave. An alternate system gave you minerals, which you could use to either buy upgrades or lurkers.
What if enemies DO get past your defense?
This depended on the specific map. Most simply kept score of how many enemies any given person had leaked; the classical variant was like this. The maps were meant to be indirectly competetive. Other maps adapted a "lives" system, which is explained more in depth in the Tower Defense node, as well as a cooperative style of play. Notable among these were the "Elements of Lurker Defense" maps, in which each player would have some special non-lurker units that were meant to represent various elements.
Origins:
No precursor to this map is known. I don't remember who made the map, but I believe he said his motive behind making it was "seeing how stupidly people use lurkers"- presumably, he just wanted to give everyone some practice in Lurker tactics.