Como posso contar o número de linhas que uma consulta MySQL retornou?

Obtendo o total de linhas em um resultado de consulta...

Você poderia apenas iterar o resultado e contá-los. Você não diz qual idioma ou biblioteca cliente está usando, mas a API fornece um mysql_num_rows função que pode informar o número de linhas em um resultado.

Isso é exposto em PHP, por exemplo, como o mysqli_num_rows função. Como você editou a pergunta para mencionar que está usando PHP, aqui está um exemplo simples usando funções 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";

Obtendo uma contagem de linhas que correspondem a alguns critérios...

Basta usar COUNT(*) - veja Contando linhas no manual do MySQL. Por exemplo:

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

Obter o total de linhas quando LIMIT é usado...

Se você usou uma cláusula LIMIT, mas deseja saber quantas linhas obteria sem ela, use SQL_CALC_FOUND_ROWS em sua consulta, seguido por SELECT FOUND_ROWS( );

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

SELECT FOUND_ROWS();

Para tabelas muito grandes, isso não será particularmente eficiente, e é melhor executar uma consulta mais simples para obter uma contagem e armazená-la em cache antes de executar suas consultas para obter páginas de dados.