From where you land in the small pillared structure, head through the noisiest grass on the planet to the gap in the rocks straight ahead and turn right to find a Rusty Coin. Head back out to the open area and take the northern exit between to rock walls. The path will split here (there is a slightly concealed path to the left and a rickety timber bridge ahead of you. Take the left path and carefully move along the trail of large footprints until you find their owner. There is a Gold Pine Resin that can be carefully grabbed by sliding along the wall in front of it.
Once it is yours, retreat back a safe distance from the monster and continue along the path while looking for a small creekbed on your right. You can walk down this and then drop off the small falls onto a ledge below. On the ledge you will find a Small Smooth & Shiny Stone to pick up. Once you have, take the only path out of there and you should arrive at a large hut embedded in a tree. Open the door and head inside.
Inside the hut, after a bit of depressing conversation you will be prompted to choose a name for your character. Once you "recall" your name, more dialogue will be forthcoming from the robed hags. You will be presented with an effigy of yourself and then get to choose your class, gift and appearance.
After the big decisions are over, head up the stairs and open the chest at the back of the room. Inside is a Human Effigy (sort of makes that gift a bit redundant). Head back down the stairs and out the back door (the one to the left of the fireplace). Right in front of you as you exit will be a bonfire to kindle. Do so. Once that is done, to the right you should spot a cart with a Soul of a Lost Undead and Torch behind it. Break the cart apart to reach the items.
Note: You can use bonfires to light torches (allowing you to see better in darkened areas)
Head through the small tunnel until you reach the narrow path with three mist doors. These mist doors lead to short optional tutorials. The first contains a Dagger (very handy if you are the Deprived class, as you will be able to use it) and teaches you basic combat. The second holds a Life Gem and teaches you about basic movement. The third brings both together. Enter and follow the instruction on the posts inside to complete them if you wish. Follow the linear path until you emerge blinking into the sunlight of Majula.