I would recommend AGAINST storing these messages either in the database or in the session, for one simple reason: tabs. (Well, really, the stateless nature of HTTP.)
Think of a person who's got multiple tabs open of different sections of your website. This person performs some action and while that loads, switches to another tab and clicks on a link. If you're storing the messages in the session/database and the switched-to tab is a page that can display these messages too, the user has now entered a race condition where depending on which request the server responds to first, the messages may display where they were not intended.
Now, there are some situations where this legitimately might not matter, but it could also be extremely confusing in some cases.
Putting the messages in the request doesn't have to be as bad as it initially seems. Perhaps you could store all the messages you want to display in the database with a numeric (or, for bonus obfuscation, hash) ID, and pass a list of IDs in the query string. This keeps the query string short, and all you have to do is keep track of what ID corresponds to what message in your code.