You can play it in any order, but here's a brief rundown of the begining to get you started. Note: I tried to hide as much as possible in order to give you direction and not ruin the game. If you're already past what I describe, just go to different places and recruit people as go along. Explore each city thoroughly and think about where that person would be if you were him/her (use this to find Relm, Locke and Mog especially).

Here we go: Once you start, go north, there should be four towns you can explore (including the one right next to you and two on the long snake like continent, there's a bridge to get to it). Once you explore them (there are a couple hidden chocobo stables I think to make the long walks easier) and "Follow a certain something/one in one of the towns" you should be able to figure out what to do next.

If you're stuck beyond this point, just say something and I'm sure some one will give you a bit more direction. But aside from this first bit, I've done all the side quests (I suppose that's what they are called, because you don't "Have" to do them) in random orders and at random levels. If you're around level 30-35, you can finnish the game fairly easily, so I wouldn't worry about going to the wrong side quest and getting pounded by enemies.