Okay I started doing the storyline quests in Gridania last night and they're really fun but I'm wondering, can I do them in all the nations or just the one I started in?
No, you can not do all of the Lvl 1 start quests for each city. However, I have read that you can pick up the Lvl 10 quests in each city, but I'd appreciate someone confirming that. I haven't personally tried it yet.
Also, how do you join guilds? Is it quest related or something?
There are the in-game guilds. These are NPC guilds that issues quests, provide rewards, sell items for guildmarks (a reward for completing guild specific quests). You can't particpate in the guild quests until Lvl 20.
Separately there are Linkshells, which are in-game player communities that you can join. They are not related to quests or anything, just used as a method for teaming up with a group of people with shared interests. SE has mentioned they have plans to evolve the Linkshells into something more once some of the foundational activities have taken place and the game is a little more established.