Databases are put together in the order they come in, right?

No, they're not. There's no guaranteed order in a relational database table, except what you impose, either with an order by clause in a query, or with a clustered index. But other than that, it's like the FAQ: "Why don't my hash elements come out in the order I inserted them?" Because it's not organized that way. Since you're using an SDBM file, you may be able to get away with it (I'm not sure), but in a RDBMS, you cannot.

What exactly is a timestamp?

In principle, a timestamp is an unambiguous, server-generated value that represents a distinct point in time. Not all database platforms support it. Furthermore, the term is frequently (ab)used to mean any column that holds the time of day.

It looks like you're on the right track, and yes, if you want to do it right, you have to remember when a message got recorded. For a working example, you can see how the Chatterbox works. Go to Everything developer site and get the Emessage 0.9.1 nodeball.