Nalbina Fortress
You start off as Reks, a 17 year old soldier whose only reason to fight is for his brother. Familiarise yourself with the controls and continue onwards until you get to some enemies and your first 'boss' of the game.
Boss: Air Cutter Remora
This is nothing difficult, attack and heal yourself when necessary. Other soldiers will heal you when you're low on HP, but it's a better idea to heal yourself as this can be infrequent. Or you could probably just stand back and let your buddies do all the work, it's your choice.
Continue through the fortress, explore if you like, just so long as you don't get KO'd you'll be fine. Reach the staircase, fight the swordsmen, there are a few cases nearby which have potions and the like in them, they don't really have any effect on the rest of the game, so don't really bother unless you're seriously strapped for curative items. Continue onward until you hit a cutscene. That's all for Nalbina.
Rabanastre
You now play as Vaan, a 17 year old street urchin who is in the middle of killing all of those pesky rats. Kill the rest, they only take a few swipes of your sword to kill, and they're all marked out as red dots on your mini-map, which is in the top-right hand corner of your screen. Once you've done this, you get a cutscene.
The place where you should next visit to continue the storyline is Migelo's place, which isn't far from where the cutscene leaves you, but it's always fun to walk around, see the sights, chat to people and so on. Migelo's place is located on your map (which comes up when you press Select), just look for a place called 'Migelo's Sundries' and head towards there.
Another scene, and you now have to find Kytes, who is at the Sandsea. The Sandsea is in the north corner of the area that you're currently at, you can also find it on your map, it isn't that difficult to find.
After another cutscene, you discover the Notice Board Hunt system, and when you agree to Tomaj's offer of more information about it that you need to hunt down a beastly vegetable known as a Rogue Tomato that's been roaming around the Dalmasca Estersand. To celebrate your first hunt, Tomaj will give you an Orrachea Armlet, which leads to a detailed explanation of the Licence system and you gain the licence for the Orrachea Armlet. He also gives you a Clan Primer (which helps you keep track of hunts). Lastly he will give you a Writ of Transit, to allow you out of the city.
Remember to equip your armlet, as you're now destined for the Dalmasca Estersand.
To get there, leave the Sandsea, head south and take the west exit as marked on your mini-map. Talk to the merchant at the fountain arguing with the Imperial Guard, and he'll ask you to deliver a Small Package to his buddy outside the gate. You don't get a reward for doing so, but the package is worth 150 Gil. It's up to you if you want to actually deliver it or not. From there, go down the stairs facing east (which is in a right direction on the map).