Делаете таблицу прочитанных сообщений со структурой user_id & id_уведомления, PK на оба поля.
Показ уведомлений:
select текст from уведомления left join прочитанные_уведомления on id_уведомления=id and user_id=? where user_id is null
И метите уведомления прочитанными созданием таковых записей.
Или можно инвертировать логику — вносить в таблицу id непрочитанных уведомлений и удалять при прочтении.
