Don't be in too much of a rush to get through to the Forest of Fallen Giants. A little time spent exploring Majula will reward you with the essential Estus Flask, not to mention a few handy bits and piece of equipment.
Find the Estus Flask and Human Effigy in Majula
Keep walking along the path, then make your way towards the fallen knight on your left to get a Divine Blessing. Turn around so that you're facing left, and then go through the opening that's just ahead of you. Make your way along these twisting tunnels, but be sure you grab the Homeward Bones and Lifegems as you do so - they're both located just after the knight on your left.
When you eventually come to a set of stairs, head up them and then walk into the structure. On your left is a door, but be prepared to deal with an enemy lurking on the other side of it. When it's dead, grab the item nearby to get hold of a handful of Lloyd's Talismans.
Do a 180 and leave this area the way you came in, travelling all the way along the path. Eventually you'll find yourself standing by a new bonfire. Light it up, then talk to the woman in green, over by the cliff to the right of the bonfire. Once you've spoken to her, you'll be given the essential Estus Flask which allows you to heal. You'll also gain the ability to level up at this bonfire after speaking with her.
Now turn around and make your way over to the hut on your left. You'll encounter a man who's managed to get himself locked out, but make sure you pop around to the right-hand side of the hut before doing anything else - you'll find a Lifegem and a Soul of a Nameless Soldier here. Once you've picked these up, go over to the far left to find a Lifegem hidden beneath a tent.
There's a doorway to the right of this tent. Go through it, then take the stairs down. Don't forget to take the Crimson Parma from the coffer in the middle of the stairway. Once you reach the next floor down, head into the hallway that's to your right.
Keep heading downstairs, and walk forward when you reach the bottom until you come to a lever. Pull it, then pass through the doorway that opens up. At the very end of this section you'll be able to pick up a Broken Thief Sword, as well as a Soul of a Lost Undead. Once you've looted them, turn around and go back up the stairs on the right-hand side. Pull the lever when you reach it.
Join the Company of Champions
Make your way back outside to Majula, and then take a left so that you're heading towards a hill. You'll soon come to a stone. Kneel before it to become a member of the Company of Champions covenant. If you look to the left of this stone, you'll see more Homeward Bones to stuff in your pockets.
Now make your way back towards the bonfire, then head all the way over to the right along the cliff edge until you're in a new hallway. Keep following the corner all the way around and you'll be able to get your hands on a Rusted Coin.
Carry on down the hallway until you come to a passage on your left. Head down it and then activate the lever that's at the end to open up the gate. Keep going along this path, and then walk over the bridge before bearing left. Walk over the plank that's just to your left, then open up the chest at the end of it to get hold of a Human Effigy. Now jump over to the area that's just behind the chest to get hold of a Soul of a Lost Undead, as well as a Homeward Bone.
With all that light looting over and done with, be warned that things are about to get a good deal more interesting from here on out. Head down the river to access the game's first main area: the Forest of Fallen Giants.