Bom, desde o começo:

<?php
mysql_connect("HOST", "USUARIO", "SENHA");
mysql_select_db("BANCO");

// Seleciona todos os registros da tabela
$query = "SELECT * FROM tabela";
$query = mysql_query($query);

// Conta todos os registros
$total = mysql_num_rows($query);

// Exibe o total de registros
echo "Total de registros: ".$total;
?>

eu utilizei a função mysql_num_rows .. não se esqueça de trocar os dados na conexao, e no SELECT .. e lembre-se, para usar a função mysql_num_rows, o QUERY deve conter o mysql_query, caso contrario, não funcionará!

ou..

$sql = "SELECT count(campo) as num_reg FROM tabela";

daí é só pegar o "num_reg" que ele vai conter o numero de registros!

Se for em scripts...
pode ser
$sql="select * from tabela";
echo mysql_num_rows(mysql_query($sql,$conexao));

ou

$sql="select count(campo) from tabela";
$registro=mysql_num_array(mysql_query($sql,$conexao));
echo $registro[0];

agora.. se vc somente quer saber isso... utilize o phpmyadmin .. ele jah retorna a qtde de registros na tabela.. ou mysql_front...

Abraços

Se quiser contar a quantidade de registros que retorna é melhor usar select count(*) from tabela.

Se quiser a quantidade de campos unicos de uma tabela faça
Select count(Distinct(campo)) from tabela (isso no mysql).

Um nome ajuda a pegar o valor me muitos casos
select count(*) TOTAL from tabela.
assim você dá um apelido para o count = TOTAL

Você deve usar a função mysql_num_rows

$tot = 0;
$select = mysql_query("Select * from table");
while (mysql_fetch_object($select)){
$tot++;
}
echo $tot; //mostrará o total de registros