The Grail is an item similar to an artifact in the sense that heroes can carry it and exchange it between them in the same way as artifacts. Also it can be sold for 1 unit of any resource. In fact, the Grail is sometimes unofficially referred to as the ultimate artifact. The Grail is typically hidden somewhere in the ground of adventure map, and finding it requires digging it with a hero. Recovering the Grail artifact and taking it to any town enables the player to build town specific Grail Building.
The primary bonuses of Grail Building for all towns are extra 5000 generation per day and 50% additional creature growth per week (rounded down). The growth bonus applies after all the modifiers: external dwellings and Statue of Legion or its components. Additionally, every town has its own unique bonuses.
Finding the Grail
In order to recover the Grail, a hero must dig it out of the ground. A hero without empty slots in a backpack cannot dig. Digging demands the whole amount of a hero's movement points so it is not possible to dig at the same day when a hero crossed even just one tile on the map. (Actually, there is a way which includes tinkering with fast/slow units in the hero's army, but good girls never do such things). Only one Grail may be hidden in the adventure map. However, it is also possible for a mapmaker to set any number of heroes and towns to carry the Grail in their backpack or have their Grail structure built, respectively. When the Grail is buried into the ground, clues to its location can be found at obelisks. Every visited obelisk reveals a part of the puzzle map, which shows the location of the Grail marked with X. Typically the X becomes visible when the entire puzzle map is revealed, but occasionally it will be shown before the last obelisk is visited. However, it is often possible to guess roughly the area where the Grail might lie, and systematically start digging it. In fact, the AI at hard difficulty levels starts digging the Grail even if only a third of the puzzle map is completed.
If the map has no obelisks, it is completely impossible to find the grail (even if every single block on the map is dug on). Also, using "nwcoracle", a cheat that reveals the puzzle map, will have no effect and the puzzle will not show anything.
When the Grail is taken to a town and the visiting hero with the Grail "visits" the Town Hall (Village Hall/Town Hall/City Hall/Capitol), a town-specific Grail Building will be built. It can be the second town building per turn, but nothing can be built on the same day after it. Also, Grail can be built in an allied town, which can be helpful if you don't have your own Tower or Conflux. All unique Grail building features will be effective for allies (except Castle, Rampart and Necropolis buildings).
Colossus is a huge golden statue of a soldier holding a sword and a shield. It increases the morale of all of the owner's heroes by +2. Although the documentation states that it increases all allied heroes morale, this appears to be wrong.
Spirit Guardian is a totem pole with a winged horse on top. It increases owners all heroes' luck by +2. Although the documentation states that it increases all allied heroes luck, this appears to be wrong.
Tower's Skyship looks like "gnome-made zeppelin". It reveals the entire map for the player who owns it, and gives extra 150 spell points bonus to the hero defending against a siege, replenishing immediately after the battle. The revealed map is a permanent effect and is not canceled if the player loses the town with the Skyship. Unlike the Lookout Tower, the Skyship cannot be used to disperse the darkness generated by a Cover of Darkness. Having this building gives a massive tactical advantage, and any player will be perfectly able to spot any attempt of siege or attack not only to this town but to all friendly heroes and buildings.
Deity of Fire is an enormous glowing devil that stands on the horizon. It causes every week to be The Week of Imp, which means that the population of Imps and/or Familiars are increased by +15 in addition to normal growth. External dwellings are not affected by this special week.
The problem with Inferno's Deity of Fire is that typically grail buildings are built long after the imps, low tier creatures, are useful. In fact, it is Necropolis who benefits more from extra imps available to be harvested as skeletons or transformed into one. 
Soul Prison (Necropolis)
Soul Prison resembles an obelisk with an upside-down pyramid halo on the tip. It increases the Necromancy skill of all the owners' heroes by 20%. Although the documentation states that it increases all allied heroes Necromancy skill, this appears to be wrong.
Guardian of Earth resembles giant skeletal humanoid embedded into the rock watching over the whole city. It increases spell power skill of the hero defending against a siege by +12.
Warlords' Monument (Stronghold)
Increases the Attack of a garrison hero by 20 when defending against a siege. This bonus gives an absurd damage bonus, able to increase the damage output of even the highest leveled creatures by about 50%, any hero holding a town with this building is nearly unbeatable except by an overwhelming army or an opposing hero with a very high level.
Increases the Attack and Defense of a garrison hero by 10 each when defending against a siege. This boost is considered to be the best in terms of siege defense, not only does it make all units tanky but also gives them a powerful damage steroid, this is particularly useful for the Fortress creatures, who have somewhat low stats (but extremely powerful and annoying abilities) and allows them to achieve a powerful combination of destruction, tankiness and annoyingness.
Fills the town's Mage Guild (*regardless* of mage guild's level) with all unbanned spells. (Excluding Titan's Lightning Bolt)*. Even spells banned on the global map can appear unless they're not banned in a town with the Grail. The best Grail building, any hero that enters the town learns all spells there are in the game. However, in games with lots of towns all the important spells may already be available even without Aurora Borealis.