Lo que te dijo el menda, esta bien siempre y cuando NUNCA borres un registro de tu tabla... Sino, lo mas facil es:
$cuantos = mysql_num_rows(mysql_query("SELECT * FROM tabla));
La consulta la podes cambiar y te cuenta los elementos que devolvio la consulta...
Saludos ;)
<div align="center"><img src="http://cablemodem.fibertel.com.ar/sainztrapaga/images/firma.jpg" width="435" height="70" border="0">
</div>