Your Gift of Exploration is, in my experience, the part of the legendary process which is most enjoyable. It involves exploring the world, doing all the heart quests, catching all the skill points, viewing all the vistas and uncovering all the waypoints and points of interest across the entire map. It is the one part of the legendary process which you will probably have completed about 50% by the time you're even considering starting going for a the much longer term legendary goal. It is also one of the only strictly plus-wealth parts of the legendary process (meaning you can't pay anyone in-game to do it for you, you can only make money doing it yourself).
Simply playing through the personal story will take you across the world, hitting loads of the above points as you go. You might be heading to your next story quest and happen across a dynamic event chain which drags you across the map, or you might detour slightly off path to grab a waypoint just in case things get a little hairy on the way. These things come naturally to the game, and that's why most people end up pretty much getting a whole chunk of this process done without even thinking about it.
If you haven't specifically focused on 100%-ing every zone you pass through, once you've completed your story line then you'll probably find you can jump back to one or two of your previous zones and just hit a couple of points before that zone will be completed (and you'll net yourself a pretty hefty exp, karma, gold and loot reward to go with it). However, even with this initial head start there will still be a significant part of the map requiring you to visit - my advice would be as follows:
Set yourself tasks to do - rather than entering a map and hoping to take it from 0-100% in an hour, instead go across the map doing odd jobs which will tick off a number of points in a zone, but not make it feel too much like a chore. For example: find your way to all the dungeon entrances. Look up an interesting jumping puzzle and make your way there. Unlock all the waypoints near the major meta events (such as the Claw of Jormag or The Shatterer).
This means that you aren't faced with a gigantic chunk of exploration to slog through when you step out of your personal story. Instead you're faced with ticking off the final few points in each of the zones, and collecting the oh-so-satisfying payday with each one.
To be honest, that is my only major piece of advice with regards to this part of the process - it is pretty straightforward. I do, however, have a couple of minor points:
1) As always, make your you're at least hitting your monthly achievements as you go. I can't really stress how important it is to hit as many daily and monthly achievements, with the karma jugs, mystic coins and laurels this will net you, believe me, you'll thank me further down the line.
2) Yes, WvW does count. Keep an eye on which colour your server is each week, and hop in to grab a couple of points. Hopefully, you will have a server which cycles through each colour regularly (allowing you to explore that part of the map relatively easily) - but sometimes you'll find you get stuck on a certain one or two colours (my server wasn't blue for a good couple of months, making it really hard to explore that part of the map unhindered) - so make sure you keep an eye out for opportunities to explore far-flung enemy territory when your server is on top.
3) The points of interest in dungeons don't count - for some reason. Neither do the new waypoints added to Orr as part of the January update.
4) Don't forget the Point of Interest in the Order of Whispers base "The Chantry of Secrets" in Bloodtide Coast. Unless you explicitly joined the Order as part of your personal story, you might not have had any reason to head into the hide-out, and there is a final point in there to hit.
Click here to read The Lazy Legendary Guide - Part 1 - The Prep