A contested territory is any zone on a PvP server where players' PvP flags are immediately turned on upon entering. Any player can be attacked by a player of an opposing faction while in these zones. Some contested territories are faction-affiliated (for example, some will only feature Alliance cities and NPC, while other will do same for the Horde), though a big number of contested zone either favor both or none of them.
About two thirds of all zones accessible by all players are considered contested. From that, about half the zones are faction-affiliated, and meeting members of the opposing faction there is still highly unlikely (for example, Ashenvale in Kalimdor and Arathi Highlands in Eastern Kingdoms, although considered contested, are still majorly loyal to the Alliance). Generally, once a player on a PvP server reaches level 20, they will be prone to start questing in contested territories. Above level 30, all worthy quests will only lead there.
Neutral cities may be located within these zones where Alliance and Horde coexist, such as Gadgetzan and Booty Bay. Trying to do PvP while near a guard in a neutral city will result in the guard becoming hostile to whoever started the fight. Both Alliance and Horde must behave while within earshot of a guard, as they'll do a little more than ask you to take it outside. Even indirect participation in a fight (i.e. healing one of the combatants) will flag the healer for PvP and bring the guards down on the player.
Battlegrounds are also contested territories, regardless of the realm type you are playing on.