The message is rendered in media/system/js/core.js
by the Joomla.renderMessages
function.
You may override it in your template with
jQuery(function() {
Joomla.renderMessages = function(messages) {
// copy / adapt the original function here.
}
});
Also, non-ajax messages can be customized by the html/message.php
template override.