Sean here is the info to add to rich:message reference
So here is what you should done now in order to customize the icon:
Besides you could use .rf-msg-ftl, .rf-msg-inf, .rf-msg-wrn in a similar way in order to customize icons for other messages severities.
You may also want to change some properties like paddings (in case your icons smaller or greater than default ones), So you could add such definitions to the same classes where changed the incons..
for rich:messages component will be almost the same but you should consider http://jira.jboss.org/browse/RF-10720 when will be fixed.