You actually have it much easier than when I went into that area and needed a map. Back then it was by quest only - but Square Enix has decided to make things much simpler for new players. You have the choice of either questing for the map or buying it from an NPC in Upper Jeuno.
Links below for info for which ever option you choose. Now this is strictly a personal opinion...but I think SE is making the game TOO easy - half the fun in the past was doing the quests and you earned exp while killing mobs during the quest or when you were farming items for the quest. Skyfiredancer (talk) 11:30, August 12, 2015 (UTC)
NPC Infp - http://ffxiclopedia.wikia.com/wiki/Rusese
Quest walk thry - http://ffxiclopedia.wikia.com/wiki/Her_Majesty's_Garden