From what I gather they'll most likely be at the Adventurer's Guild in each city-state.

Ul'dah: The Quicksand hosts an inn near the retainer bell called "The Hourglass".
Limsa Lominsa: The Drunken Wench has an inn labeled "The Mizzenmast".
Gridania: At the Carline Canopy you can find an inn they call "The Roost".

So it's my guess the quest will either start with that city-nation's proprietor (Ul'dah's Momodi, Limsa Lominsa's Baderon, or Gridania's Miounne) or the innkeeper found at each desk in the Adventurer's Guild. In fact the Adventurer's Guild linkpearl you obtain earlier on might even be used to start the quest. The proprietor who gave it to you will contact you about getting a room of your own and send you off on some task to fulfill and obtain your own room. But the question still remains if you'll be allowed to get a room in each city, if there will be quests for each city or just one single universal one to unlock a room at each inn.

EDIT: Kiri beat me to it.