Deberías especificar que Base de datos usas ..
En principio .. si usas Mysql tienes (como en toda BD) dos formas de hacerlo:
1) vía SQL .. la más óptima si sólo buscas ese total de registros de tu consulta SQL dada.
SELECT COUNT(*) FROM tabla WHERE condiciones si las necesitas ...
2) Vía funciones de PHP. Útil si ademá de querer obtener ese total .. también vas a trabajar con el resultado que se obtenga ("record-set").
mysql_num_rows()
www.php.net/mysql_num_rows()
Un saludo,