whenever you hit a new area, ask the guards for directions to some things. once you do, it will flag it on your map.
like sterlingedge said, there's a lady near goldshire who can show you. i started at around lvl 9 or 10..i could have tried it as soon as i hit goldshire seeing as there are so many beasts around. but on the other hand, you'll be killing many more beasts so you're really not behind, either.
not to mention, when you hit goldshire the first time, you might not have extra bags for inventory.