The original DotA was a mod for Warcraft 3. Basically, it's an RTS where you control a single unit (a Hero) and level them up from level 1 in every match. The objective of the game is to push "lanes" in a map back to the other team's base where their central building is. If you destroy their main structure, you win. Each lane has a certain number of turrets which defend the enemy's base, and you have to destroy these turrets to advance. You also get NPC minions that spawn in waves from your base to assist you in pushing lanes.
I'll keep it at that. The wiki page has all the info you need. Valve could have easily made some changes to the mechanics in DotA II but I doubt it's anything major.
There's two other games that are like DotA called League of Legends and Heroes of Newerth. League of Legends is free to play and in my opinion is far better than Heroes of Newert, which isn't free and has a comparatively horrible user base). HoN's graphics are like 10 times better than LoL's but their art style is really...runny I guess. Dota II is going to kick both their asses I think.
Anyway, that was a great trailer. It wasn't like other Valve trailers, but I still think it was amazing to watch. Source still looks beautiful in my opinion.