From Krakiipedia, the unofficial free GemStone IV encyclopedia.
Deeds are granted to mortals of Elanthia by the goddess Lorminstra in exchange for donation or sacrifice of some sort. Deeds are essentially a pact with the goddess which grants the deed-holder a chance to walk Elanthia again upon their death, and avoid passing through the Ebon Gate into Eternity.
In the past, dying without deeds caused one to go "demonic", a horrible fate resulting in the permanent destruction of the adventurer and all their belongings. However, this ceased to be the case with the introduction of Death's Sting. It is no longer absolutely necessary to possess deeds.
Calculation for Cost
101 + (level * 100) + (deeds * 100)
Example: a 99th level character with 7 deeds = 10701 silvers
If using items (usually gems), a general estimate is 3x what they appraise for. Using the example would mean a gem worth 3567 silvers. Err on the side of caution with this. The gem bonus does not seem to apply (at least not as substantially) in Ta'Vaalor, but wands seem to apply to the 3x bonus, so they are a suggested substitute.
Different Deed Formulas
Gamemaster Xayle July 9th 2012
Locations for Obtaining
All players can obtain deeds in Wehnimers Landing (lich room 4045), Rivers Rest (lich room 10854), and in Ta'Illistim (lich room 745). 20th level players and above can obtain deeds in the Hearthstone garden.