The first one came out 94.
Warcraft 3 came out in 2002, but the expansion pack Frozen Throne (which is what most of the people play) came out 2003.
To go online you load up the game and start up the main menu, and I believe it said Multiplayer or Blizzard Online or something, I haven't played it in a year. You then connect to an online lobby that is divided by channels, you can either create a custom channel or join an official channel that is already there. You then go to "Find Games" I think, or you can host your own game. It will load up games, and you can select which one you want to join.
The AvP map would be listed with the other games if someone was hosting it, or you host it yourself and wait for others to join.
