Yo tengo hecho algo así en mi buscador:
Código PHP:
$totalRows = mysql_num_rows($query);
if(!empty($query)){
echo stripslashes("<p>Su busqueda arrojo $totalRows resultados para <strong>$frase</strong>");
while($row = mysql_fetch_array($query)){
//aquí muestro los datos de todo lo encontrado
}
}