In ogni pagina memorizzi il momento in cui l'utente ha visitato il sito, con una query del tipo:
Codice PHP:
// supposto che la tabella si chiami 'utenti' e il numero di ognuno sia 'id'...
// memorizzo il timestamp attuale
$sql = "UPDATE utenti SET lastaction=".time()." WHERE id=".$idutente;
mysql_query($sql); 
Per selezionare dal database gli utenti che hanno visitato il sito da meno di 5 minuti puoi fare una cosa del genere:
Codice PHP:
// imposto l'intervallo massimo dall'ultima visita affinchè l'utente venga considerato online
$intervallo = 300; // si misura in secondi, quindi 5 minuti sono 5*60 secondi

$ora = time(); // timestamp attuale

// eseguo la query di selezione
$sql = "SELECT * FROM utenti WHERE lastaction>".($ora-$intervallo);
$query = mysql_query($sql);

// ottengo il numero degli utenti online
$totale = mysql_num_rows($query);

echo "Attualmente ci sono ".$totale." utenti online:

";

// estraggo i dati degli utenti online in un array e con un ciclo li mostro
while ($dati = mysql_fetch_array($query)) {
    echo $dati['nome'].'
'; // mostro il nome dell'utente
} 
Se non hai capito qualche passaggio chiedi pure.