Leveling on a PvP server is little different from leveling on a PvE server; most "overworld" PvP is dead, and when it does happen, it's more likely to be level 85's ganking lowbies in Stranglethorn vale (because they can!) rather than two groups spontaneously forming to, say, kill all the quest NPCs in Tarren Mill.
Perhaps more relevantly, the types of combat you're likely to find on a PvP server outside of instanced PvP is not going to be representative of instanced PvP. Put another way -- ganking and getting ganked won't be particularly helpful in making you a better PvPer, because the battelgrounds and arena that represent the PvP endgame in world of warcraft don't revolve around 1 on 1s and ganking.
The truth is that despite the population of a server, it's still relatively uncommon to run into other players except in areas that encourage close proximity (whether due to daily quests, or anything else).
In my experience on a PvP server during the Burning Crusade and Wrath of the Lich King, the places most likely to run into PvP was "Isle of Quel'Danas", The southeastern plateau in Terrokar forest with the Skywing(skyband?) daily quests, and the naxxramas meeting stone.
I would go so far as to suggest that it's not worth your time. Conceivably, you'd get just as much PvP experience fighting consecutive duels outside of Ironforge or Orgrimmar.