¿Cómo puedo contar el número de filas que devolvió una consulta de MySQL?

Obteniendo filas totales en un resultado de consulta...

Podría simplemente iterar el resultado y contarlos. No dice qué idioma o biblioteca de cliente está utilizando, pero la API proporciona un mysql_num_rows función que puede decirle el número de filas en un resultado.

Esto se expone en PHP, por ejemplo, como mysqli_num_rows función. Como editó la pregunta para mencionar que está usando PHP, aquí hay un ejemplo simple usando funciones mysqli:

$link = mysqli_connect("localhost", "user", "password", "database");

$result = mysqli_query($link, "SELECT * FROM table1");
$num_rows = mysqli_num_rows($result);

echo "$num_rows Rows\n";

Obteniendo un recuento de filas que coinciden con algunos criterios...

Simplemente use COUNT(*) - consulte Recuento de filas en el manual de MySQL. Por ejemplo:

SELECT COUNT(*) FROM foo WHERE bar= 'value';

Obtener filas totales cuando se usa LIMIT...

Si usó una cláusula LIMIT pero quiere saber cuántas filas obtendría sin ella, use SQL_CALC_FOUND_ROWS en su consulta, seguido de SELECT FOUND_ROWS( );

SELECT SQL_CALC_FOUND_ROWS * FROM foo
   WHERE bar="value" 
   LIMIT 10;

SELECT FOUND_ROWS();

Para tablas muy grandes, esto no va a ser particularmente eficiente, y es mejor ejecutar una consulta más simple para obtener un conteo y almacenarlo en caché antes de ejecutar sus consultas para obtener páginas de datos.