Displaying Messages and Notices

[eluser]BrandonDurham[/eluser]
I'm looking for a simple way to display friendly messages to the user when actions are taken or when an action can't be performed—something like, "The ___________ entry has been updated" or "I'm sorry, that entry is locked and cannot be updated". How do you guys like to do this?

The problem I'm having is that I often use redirects after forms are successfully submitted to essentially clear all POST data, and I can't think of a clean way to display a message on the new page.

I appreciate any suggestions. Thank you.