The layout of Magento’s information, warning and error messages cannot be easily changed using layout and template files. The HTML generation is done from a Block PHP class (Mage_Core_Block_Messages). It is a very bad idea to overwrite any core element of Magento. Instead we are going to extend this core-block by creating a separate module.
My goal was to make the messages compliant with Twitter Bootstrap alerts but the following technique can be used for about anything.