http://se.php.net/manual/it/function.mysql-num-rows.php

$risultato = mysql_query("SELECT * FROM categorie ORDER BY nome_cat", $connessione);
$num_righe = mysql_num_rows($risultato);

e poi fai l'if

if ($num_righe > 0)
{
stampi tabella
}
else
echo "Non ci sono record".