Ti crei una tabella con un id per ogni messaggio.
La data puoi anche farla coincidere con quella di inserimento senza bisogno che sia l'utente a doverla inserire. Questo lo puoi fare sia con la funzione date() e i vari parametri di php che direttamente in mysql. Non ricordo il tipo di campo che prende la data in automatico.
Per la visualizzazione dal più recente al più datato metti l'ordinamento desc alla query.