The only species that we know for sure have queens are Mudokons, Glukkons and Sligs.
Alf suggested that Slogs have queens, but take anything he said with a grain of salt.
As for Steef, Paramites, Scrabs and Fleeches, we just don't know. Popular fan opinion is that Paramites do have queens, Steef and Scrabs don't, and Fleeches are just ewww.
EDIT: I'm not sure how much credence we're putting in Matt Lee these days,
but he says that Paramites do have a queen and Scrabs don't.