Quiero aclarar que acabo de encontrar como hacerlo. Se los pongo aqui por si a alguien le interesa.
Código PHP:
$link = mysql_connect($host, $user);
mysql_select_db($db, $link);
$result = mysql_query("SELECT * FROM gal_imagenes", $link);
$total_registros = mysql_affected_rows();
//Esto me guarda en la variable $total_registros el total de registros en la tabla