Well, this was simple.
It is almost the same as doing a count in a MS SQL or MySQL query, only you don’t specify a column name or a * inside the parenthesis.
SELECT count() FROM SalesForceObject
So for example if you wanted to know how many User objects, you could run this SOQL query:
SELECT count() FROM User