On the new cataclysm map, the barrens has been split in two by lava.
How will the people that are leveling travel from the Northern Barrens to the Southern Barrens?
According to Wowwiki (although I can't find where it's getting its info from):
On foot or by flight path from Crossroads to Desolation Hold or Ratchet to Desolation Hold, Fort Triumph, or Northwatch Hold.
I'm guessing, though, that since Northern Barrens is 10-20 and Southern Barrens is 30-35 (at least according to everything I've read), you won't want to walk directly from one zone to the other.
Well, first thing to remember is that the zones don't have continuity. North Barrens is a 10-20 zone for the horde. South Barrens is a contested 30-35 zone for both factions, designed to encourage world PVP through a lot of cross-faction contact and antagonistic questing. (think Southshore and Tarren Mill 2.0 in the design).
As for how to get there? Well, barring the construction of a bridge across the Divide, (unlikely), the easiest way is to just walk right in, from Mulgore to the West, or take the Great Lift up from Thousand Needles to the South.
Looking at maps, it also appears that the footpaths Southeast out of the Stonetalon Mountains may skirt the southern edge of the Divide allowing for access to the South Barrens as well. This makes the most sense from a zone flow standpoint, as Stonetalon will be a 20-30 zone, allowing for a clean progression of North Barrens(10-20) -> Stonetalon(20-30) -> South Barrens(30-35) -> Thousand Needles(35-45) -> Tanaris (45-50) ->Un'Goro(50-60).
Well in the new expansion you will be able to fly on a mount but thats higher levels...Blizzard is probaly going to have some sort of bridge fallen tree.
I just learned that jumping into the Great Divide near the Stagnant Oasis in Northern Barrens will spawn you in Southern Barrens.
If you're bent on doing this despite the non-continuity of the levels, and you're horde, then you can take the zeppelin from Orgrimar to Thunder Bluff and jump near hunter's Hill. The Zep flies quite close to the ground at that point and you should suffer no damage if you time it right. you can then walk to hunter's hill and get the Flight path so you can return to crossroads.