After you get the paraglider from the old man, he says to go east to Kakariko Village to meet with Impa.
Leave the Great Plateau
To start your journey toward Kakariko Village, warp to the Great Plateau Tower, then look east. You should be able to see a tower to the east, just before the Dueling Peaks mountain. You should go in that direction, so you might want to use your Sheikah Scope to put a pin on it so that your minimap will show which direction to go in. The Seek Out Impa destination will also give you a general idea of the direction to go in.
Then you can just jump or fall off of the tower and press X to use the Paraglider, but keep an eye on your Stamina Wheel. If you are worried that it will run out, you can press B to freefall until you are closer to a safe place to land, then take out the paraglider again to slow down before you land.
As soon as you set foot in uncharted land, "Hyrule Kingdom" will appear on the screen. At this point, you can find Korok Seeds, and if you purchased the DLC, the DLC side quests will be added to your Adventure Log.
The Outpost Ruins are just east of the Great Plateau Tower. If you explore the ruins, you can find a chest in one of the buildings. It contains a Traveler's Bow.
East Post Ruins
From there, go east to the East Post Ruins, and be careful of the Moblins and Bokoblins there.
Keep going east toward the tower and you will reach the Proxim Bridge. Talk to the guy standing on the bridge, and he will show you a nearby shrine. This is the Bosh Kala Shrine.
Keep going toward the tower. As you go along, look for a giant hollow log on the right. If you go through it, you will see a flower inside. Try to take the flower, and it will disappear, then reappear farther ahead. Keep following the flower, and when you find the last one, a Korok will appear and give you a Korok Seed.
From there, glide down toward the tower, and land before the small forest on the right. There is a hole in the ground, and a boulder nearby. Push the boulder to roll it into the hole, and another Korok will appear and give you a Korok Seed.
Just before the Dueling Peaks Tower, there is a Bokoblin camp. Defeat them all to unlock the treasure chest. It contains a Soldier's Shield.
As you go toward the tower, you find some fast-moving water in the way, but there are some rocks going across the water. Go to those rocks and use the Cryonis rune to help you get across. Some Bokoblins will attack on the other side. After you deal with those Bokoblins, look for a slope going upward with more Bokoblins on it. Go up that slope and kill the Bokoblins. From there, look down at the base of the tower. There are some rocks on the left side that are leaning against the tower. Glide down to the base of those rocks, where you will find some cracked rocks that you can open with a bomb. You will find a chest that contains a Soldier's Spear.
Climb Dueling Peaks Tower
Now you should walk up the rocks to reach the tower. There are plenty of ledges on the tower, so there is no danger of running out of stamina as you go up. At the top, check on the pedestal to activate the tower.
After receiving the map of the area, your Sheikah Slate will activate a new power: the Sheikah Sensor. It will react if there is a Shrine nearby. You have to move around for the Sheikah Sensor to tell you if you are going in the right direction.
If you are not moving, you can still look at the center of the Sheikah Sensor indicator at the person icon for information: if the person icon is glowing, there is a shrine somewhere nearby. But if the person icon is dark, the Sheikah Sensor doesn't detect any shrines in the area.
You can change the Sheikah Sensor settings from your map. Open the map and press Y to show the Sheikah Sensor settings. You can turn it off from this menu.
Find the Shrine
The Sheikah Sensor detects a shrine nearby. Look down at the base of the mountains to the east and you should see a ledge with a mushroom growing above it. Glide down to this ledge and follow the path as it goes between the mountains. You will see ore deposits on the cliff wall. Hit these with a durable weapon like the iron sledgehammer, and you might get amber, flint, rock salt, and other ore.
Keep following this ledge until you find the shrine that the Sheikah Sensor has been reacting to. It is the Ree Dahee Shrine.
Continue Going East
After you exit the shrine, keep going east. The ledge ends, so go down to the lower area. There are some cracked rocks on the left, so bomb them open to reveal a chest. It contains a Traveler's Bow.
Farther east, the Sheikah Sensor will react to another shrine. There are some Bokoblins up ahead. If you want to avoid them, climb up to the ledge along the wall and they won't see you. If you want to get their treasure, you can use Magnesis to drop a magnetic boulder on the bomb barrels near the Bokoblins. This should kill most of them. If you kill the rest, you can get a Boomerang from the chest. To throw it, make sure that it is equipped, then hold the R button to aim, and let go of R to throw it. If you are standing near the same spot that you threw it from, you can catch it when it returns if you press A.
The next shrine is surrounded by spikes, so climb up to the ledge on the left side (east of the Bokoblin camp) and go around the path until you can see the shrine in the water. Float down to it with the paraglider. It's the Ha Dahamar Shrine.
Get a Horse
After you complete the Ha Dahamar Shrine, the spikes go away, so you can walk over to the nearby building. This is the Dueling Peaks Stable. You can talk to people there to learn about how to catch a horse.
If you have the Super Smash Bros. Link amiibo, you can use it to get a special horse that has good attributes, is already tame, and comes with a name. Ride this horse to the stable to register it. You can enable the amiibo rune in the Sheikah Slate from the Options Screen in the Start menu.
If you don't have the aforementioned amiibo, or just want to catch a wild horse, look for horses in the grass north of the stable, then crouch down by pressing the left control stick like a button. Go slowly toward the horse (but avoid standing directly behind it because it could kick you), then press A to hop on. Press the L button to soothe the horse if it does not obey you, or to thank the horse if it does what you want. Your bond with the horse will become stronger the more you ride the horse. Once your bond reaches the maximum level, that horse will always obey you.
If you want to keep a horse, ride it back to the Dueling Peaks Stable and talk to the guy at the outside counter. Choose to Register the horse. You will be asked to name the horse. You can't change this later. From then on, you can board the horse at the stable and take it out any time at any stable that you find. A horse with a strong bond will automatically follow roads.
Horses can get hurt by monsters and other dangers. If a horse dies, there is a way to get it back if you find a certain place.
Go north from the stable and keep going north at the fork in the road. You will cross the Kakariko Bridge. Keep following the path and you will see a strange green guy next to a tree. This is Hestu, a Korok whose maracas were stolen. This starts The Priceless Maracas side quest. Go through the stone arch up the hill and defeat the monsters there to get Hestu's Maracas from the treasure chest. Then go back and give Hestu the Maracas.
If you give him Korok Seeds, he can add slots to your weapon stash, shield stash, and bow stash. If you haven't found any Koroks yet, you can find Koroks hiding in many places around Hyrule. Usually there is a puzzle where they are hiding, but sometimes they just hide under rocks on top of hills and mountains, or sometimes they can be found by following trails of sparkles. There is a puzzle farther up ahead where you can find a Korok, if you haven't found any yet.
After you have Hestu expand your stashes twice, he will say that he needs to go back to Korok Forest. Talk to Hestu again to ask him where it is. He says that it is to the north, and that if you follow Hylia River north, you will reach the forest.
Continue to Kakariko Village
Continue going north along the path. Look for a metal puzzle in the wall. Use Magnesis to move the small metal block into the upper-left corner of the shape on the bottom-left. Then a Korok will appear and give you a Korok Seed. If you haven't already given Hestu a Korok seed, you can go back and give him this one.
As you go closer to Kakariko Village, the Sheikah Sensor will detect another shrine.
Enter the Village
When you arrive, you will find Nanna sitting by a campfire. She seems to be injured. If you talk to her, she shows you where Impa's house is.
After this, follow the path toward the town. Before you go down to where the houses are, go up the slope that goes up past the houses. If you are going the right direction, your Sheikah Sensor should be reacting strongly. The path will curve to the right, where you will find the Ta'loh Naeg Shrine. Open it so you can easily warp back to this village. If you rode your horse here, you can warp back to the stable and talk to the guy at the counter and choose Board Horse. They will go get your horse and take it to the table.
Talk to Impa
From the shrine, you can glide down to Impa's house. Impa lives in the largest house in the village. If you talk to the guards in front, they will block your way at first, but then they will notice your Sheikah Slate and apologize.
Go up the stairs, and you will meet Paya. After talking with her, go inside, and there will be a cut scene. After Impa tells you about the message that Zelda gave her, you can talk to Impa again and say "I am." Impa will tell you what has happened over the last 100 years.
After a cut scene, the quests "Free the Divine Beasts" and "Locked Mementos" will be added to your Adventure Log in the + menu. The "Seek Out Impa" quest will be completed.
You are free to do the quests in any order, or just explore freely. But it is helpful to complete the Locked Mementos quest next.