How do I reformat status messages?
the function you need to hook is:

themename_status_messages()

where themenameis your theme's name. You can see the status message theme docs here.

What specifically are you trying to restyle? Most of it can be done with CSS, without introducing a theme hook.