¿Cuál es la mejor manera de obtener el número total de registros en una tabla mysql con php?

Te dijeron correctamente. mysql puede hacer este conteo por usted, lo cual es mucho más eficiente.

$result = mysql_query( "select count(id) as num_rows from table" );
$row = mysql_fetch_object( $result );
$total = $row->num_rows;