A few months back at work we had the requirement for a Magento gift extension which turned out to be more of a hassle than one would think. After weeks of testing the variety of modules out there the decision was made to write our own.
Lucas wrote the module in his own time and is now marketing the extension via proxiblue.com.au. The extension brings a few nice features not offered by other extensions such as using existing products as gifts and gift quantity limits. The extension is also compatible in multi-store configurations.
I can highly recommend the Magento Gift Promotions extension.