You'll need a field in your message table that stores the date the message was added. You could rely on an autoincrementing field, but a proper "dateadded" field offers so much added value for so little cost it's not funny. It could be a MySQL date type, or a large integer type holding a Unix timestamp; either way, the method for sorting it would be the same:
"SELECT * FROM messages ORDER BY dateadded DESC"
The key bit is the 'DESC' for descending order. There's also an 'ASC', but ascending is the default order anyway.
Note that this relies on the dateadded field being the right type - one that MySQL will sort properly. A string field containing dates like '23 Jan 2001' won't work.
