Como contar registros especificados de uma tabela

Boa tarde Senhores,

Bom, estou desenvolvendo um sistema e gostaria de mostrar um relatório dos registros, dizemos assim.

Por exemplo, quero mostrar quantos usuários tem dos estados.

Se tenho 20 registros na tabela, 6 de MG, 4 de SP, 5 de RJ e 5 RN. Quero que apareça, sendo que será de todos os estados do Brasil.

Como posso proceder com estas informações em PHP (claro) com banco de dados MySQL. Não tenho nada pronto ainda e tenho uma boa lógica de programação, não sei o que usar. mysql_num_rows, SELECT count(*), etc..

Aguardo, obrigado.