Like this:
SELECT s.statename, COUNT(c.cityid) AS CountOfCities
FROM cities as c LEFT JOIN states as s ON c.stateid = s.stateid
GROUP BY s.statename
As Manfred R. Bihy wrote in comment, if you would like to get all states and cities, even if state has no city - probably it's impossible ;) - you need to use query like this:
SELECT s.statename, COUNT(c.cityid) AS CountOfCities
FROM states as s LEFT JOIN cities as c ON s.stateid = c.stateid
GROUP BY s.statename
Thank you Manfred ;)