The SQL you need is something like:
SELECT category_name, COUNT(*) AS total FROM category_table
GROUP BY category_name
This will return a result set that has one row for each category. Each row has two columns: the category name and the total number of records with that category name. The same technique works for category id's or any other key you may want to use.
You would use it this way:
$sql = 'SELECT category_name, COUNT(*) AS total FROM category_table '.
'GROUP BY category_name';
$db = new PDO($database, $user, $password);
$results = $db->query($sql)->fetchAll(PDO::FETCH_ASSOC);
// $results is now an array with the query results
Edit: added sample PHP code.