cada que cargas una pagina haces una mini-consulta a la BD, como:
$msgs=mysql_query("select ID from mensajes where destinatario=$userID and status=0");
luego cuentas los registros:
$cuantos=mysql_num_rows($msgs);
Luego, si hay mas de un msg no leido (status=0), mandas un javascript al navegador...
Código PHP:
if ($cuantos>0){
$java= "<script language='javsascript'> alert ('Tienes mensajes nuevos');</script>";
}else{
$java="";
}
Despues en tu head de html, metes algo así:
<html>
<head>
<?= $java; ?>
</head>
etc...
Esa es la idea, que puedes hacer tan compleja como tu quieras...
Saludos!