A resposta de Jeremy Ruten acima é boa e executa rapidamente; por outro lado, fornece apenas o número de linhas e nada mais (se você quiser os dados do resultado, precisará consultar o banco de dados novamente). O que eu uso:
// only ask for the columns that interest you (SELECT * can slow down the query)
$query = "SELECT some_column, some_other_column, yet_another_column FROM `table`";
$results = mysql_query($query, $connection);
$numResults = mysql_num_rows($results);
if ($numResults > 0) {
// there are some results, retrieve them normally (e.g. with mysql_fetch_assoc())
} else {
// no data from query, react accordingly
}