come flag di lettura puoi usare un cmapo TINYINT(1) in cui memorizzi 0 [letto] 1 [da leggere]... o viceversa.. fai tu

chiaramente, non ci avevo pensato prima, puoi memorizzare anche l'oggetto del messaggio e la data.. e altre cose che vuoi... vedi tu...

riguardo a come realizzare il resto... dipende molto da come tu gestisci gli utenti.. se hai utenti loggati con sessioni semplicemente ti mantieni in sessione lid dell'utente nel database... quando un utente clicca su un apposito link per mandare un pvt ad un altro utente passi in querystring l'id dell'utente destinatario... a quel punto hai l'id del mittente, l'id del destinatario e quando l'utente invia il form lo inserisci nel database con questi dati...

per il resto fai due paginette:
ricevuti: una semplice query che prende tutti i messaggi nel cui campo destinatario ci sia l'id dell'utente che apre la pagina dei messaggi ricevuti
inviati: similmente con il campo mittente