In MySQL: (if that's relevant)
I've got my 'users' table.. that looks a little like this :
iD, email, password.. blah
And I have my messages table (that I haven't created yet):
iD, user_sent, user_received, message
iD, is obviously the message iD.
user_sent, is the user that sent it's iD
user_recieved, is the user that's receiving it's id
message is the message

Now this just screams bad structure to me, what's a more logical approach?