*Warning, minor spoilers of Dark Souls lore may follow. If you are a curious and ambitious mind eager to discover things on your own, then, in the words of Walter White: tread lightly"
Dark Souls takes place in the fictional realm of Lordran, a land which the gods have forsaken, inhabited by undead human beings who are cursed with eternal life.
In the beginning, the universe was under the dominion of the dragonkin, who ruled with an iron fist. However, once the Lords of Fire came into this world, they cast light upon the darkness and challenged the rule of the everlasting dragons. The four most powerful lords were Nito, the first sentient being that had died, now ruling as the lord of death; the Witch of Izalith and her daughters of chaos, mighty pyromancers who could wield the flame as a powerful weapon; Gwyn, the lord of sunlight and the ruler of these lords; and the furtive pygmy: a deity who was the owner of the "dark soul" and claimed to be "so easily forgotten" by history.
These lords, with help of the dragon "Seath the Scaleless" who betrayed his own kind, defeated the dragons and ushered the world in an era of light. The gods took to living in the great city of Anor Londo, and all was well in the universe. However, the gods realized that their golden rule would come to an end once the fire died and the darkness spread. Un-eager to give up their power, Gwyn sacrificed himself in order to kindle the First Flame (the very first fire lit in the world and a central element to the power of the lords) and prolong the Age of Fire. This drastically altered the course of nature, as the fire is meant to die out and return in time. In turn, humanity was cursed with undeath, with many becoming marked with the Darksign, a circle of fire branded upon the persons chest, signifying their un-ability to truly die.
This is where you, the player, come into the picture. You assume the role of one of these undead souls, locked up in the Undead Asylum where you hopelessly await your "hollowing", a state of existence in which the undead has lost his/her sanity and become hostile towards all beings, living or dead. However, fate seems to be on your side as you are rescued by a mysterious knight, who gives you the key to your freedom. He later tells the player character about the prophecy of "the Chosen Undead", an undead who will escape from the Undead Asylum, ring the "Bells of Awakening" and hopefully, break the curse of undeath. The player manages to find his/her way out of the asylum, and ends up at "Firelink Shrine", a location which will come to serve as the base of operations to the player.
From here on, you are mostly free to go wherever you want in Lordran. The recommendation however, would be to head up towards the Undead Burg, which serves as a fine area for beginners to hone their skills. If you have not decided which class you want to begin the game with, then check out the Beginner's Guide/Classes section!