Hola, supongo que querrás hacerlo con bases de datos. Podrías crear una tabla con los siguientes campos:
id - int
remitente - id del usuario registrado
destinatario - id del usuario registrado
asunto - varchar
mensaje - text
fecha - bigint
leido - boolean o char(1)
Si quieres que los usuarios puedan crear carpetas para organizar estos mensajes podrías añadir el campo carpeta - varchar
La programación debería ser sencilla a partir de esta tabla. Si tienes cualquier duda coméntalo.
Salu2,
Avalon