Since the time of the Ancient Mesopotamians (at least), it has been a common practice to put some special item into the foundation of important buildings. These items were intended to please the gods or ward off demons, or in more modern times, simply bring good fortune or keep up with old traditions.
In Mesopotamia inscribed clay tablets, cones, and cylinders were buried inside brick boxes underneath the city walls, covered with boasts of the king's grandeur and generosity. These tablets were indeed not only good luck charms but outright bragging, as some of them included requests to future builders to transfer the tablets to newer constructions so that the reputation of the original builders might not be forgotten. In Ur bronze figurines have been found, and some archaeologists hypothesize that animal, or even human, sacrifices may have been a part of some rituals surrounding foundation deposits.
In ancient Egypt items were often buried in specially-dug, brick-lined chambers, and contained much the same sort of goods you would find in a tomb. Food, ceremonial objects, and both full-sized tools and miniature models of tools were common. These chambers were most likely intended to protect the buildings from harm, acting as a offering to gods that would watch over the buildings. The positioning of these chambers depended on the type of building; for example, temples had deposits at each corner, while tombs had deposits by their entrance, although in any building additional deposits might also be placed in various locations.
The practice of including foundation deposits has been taken up by many cultures. Persian King Darius included silver and gold tablets in the foundation of his grand palace in Persepolis. The practice continued in Ancient Greece and Rome, where the tradition of creating small chambers to contain the deposits was dropped, and items were simply buried. The Romans, in particular, are well-known for including jumbled deposits of coins in the foundations of their buildings. This practice is still carried out today, at least in America, and it is not uncommon see a coin embedded in the concrete of a new sidewalk or doorstep.
Many cultures have included various types of sacrifices and ceremonies when building large constructions (which were often temples or other constructions with ties to the gods). It is often hypothesized that these foundation deposits are replacements for an earlier tradition of sacrifice. Indeed there are stories of human sacrifice in Europe until just a few centuries ago.
"It is related that in Oldenburg in Lower Saxony children were buried alive as late as the seventeenth century in order to make the dikes secure."
-- Byron, the Bible, and Religion By Wolf Z. Hirst
These tales of child sacrifice are quite pervasive in Western Europe, apparently particularly so in Germany. It is said that Gypsy children were sacrificed by being buried alive in order to bring good luck to structures such as dikes. While this has entered into the popular mythology of Germany, I have not been able to find any archaeological or historical information on how common these practices might have been, or if they even existed.
Die Rituale der Deichbauern verlangen aber, dass „etwas Lebendiges“ im Deich verbaut werden muss. Zuweilen hatte man früher Zigeunern Kinder abgekauft und diese lebendig in den Sandmassen begraben. Doch Hauke untersagt diesen Brauch beim Bau seines neuen Deiches – als die Arbeiter einen Hund eingraben wollen, rettet er diesen – und so sehen viele einen Fluch auf diesem Deich lasten.'
The rituals of the dike builders required, however, that "something living" be built into the dike. Earlier, one sometimes would buy gypsy children and bury them alive in the mass of sand. However, Hauke forbade this tradition during the construction of his new dike – when the workers wanted to bury a dog, he rescued it – and so many believe this dike to be cursed.
-- From the German Wikipedia article on the novel Der Schimmelreiter by Theodor Storm.
There are also a handful of European fairy tales about children being sacrificed by being buried alive (or perhaps horror stories might be a better descriptor?). Some of these children are buried simply in order to stop a great evil (such as the black plague), while other are specifically used as an aid for construction.
When Christianity was introduced to Rügen, they wanted to build a church in Vilmnitz. However, the builders could not complete their task, because whatever they put up during day was torn down again by the Devil that night. Then they purchased a child, gave it a bread-roll in one hand, a light in the other, and set it in a cavity in the foundation, which they quickly mortared shut. Now the Devil could no longer disrupt the building's progress.
It is also said that a child was entombed in the church at Bergen under similar circumstances.
-- Rügensche sagen und märchen, Das eingemauerte Kind ('The Entombed Child') by Alfred Haas. (This page has a more detailed (German) version of the story.)
So maybe it's all just fairy tales. But it is generally accepted that human sacrifices were used, thousands of years ago, as foundation deposits in the Near East. Some scholars even think that this practice is described in the Bible, when King Heil rebuilt Jericho:
1 Kings 16:34 In his days did Heil the Bethelite build Jericho: he laid the foundation thereof in Abiram his firstborn, and set up the gates thereof in his youngest son Segub, according to the word of the LORD, which he spake by Joshua the son of Nun.
Until recently it was quite common to include a 'time capsule' type deposit in the cornerstone of skyscrapers and other large constructions. This might be seen as a compromise: we're not making an offering (how heathen), but we are still surrendering items of value to commemorate the construction of the building. These days the time capsule business has moved from skyscrapers and government buildings to schools and universities, but they are still often put into the cornerstones of new constructions. It is worth noting that these capsules are still a type of sacrifice in the literal sense; they often include electronics that are valuable today, but will be useless and largely uninteresting when the capsule is finally opened (iPods and Palm Pilots and the like).
In England you may still find people burying various oddments under a newly constructed threshold, a practice common throughout the ages: in Assyria clay figurines were buried, while in some Islamic countries incantation bowls might be used. In England the witch bottle is probably the most famous threshold item, a bottle filled with a miscellany of old scraps such as buttons, nails, urine, and human hair. These were used until at least the late 1800s to ward off witches. In all these cases the threshold items are specifically used to prevent evil spirits and evildoers from entering the home.
Having said all that, I just poured the foundation to my house, and the only foundation deposit that anyone even considered was to write their initials in the cement. Obviously, the modern homeowner is spiritually bankrupt, and not a little vain.
References:
Time capsules By William E. Jarvis
Digging Up Biblical History by J. Garrow Duncan