Consequentialism decides between actions only by reducing them to expected outcomes (or probability distributions over outcomes), and comparing those outcomes. Utilitarianism is consequentialist, but with additional structure to how it compares outcomes. In particular, utilitarians combine uncertain outcomes by weighting them linearly with weights proportional to probability. Additionally, many (but not all) utilitarians also subdivide their utility functions by agent, specifying that individuals' preferences are to be quantified and linearly combined.
Hm, that's not how I was breaking it down. We really haven't standardized on terminology here, have we? That would be a useful thing.
Here's how I was using the terms:
Consequentialist - Morality/shouldness refers to a preference ordering over the set of possible universe-histories, not e.g. a set of social rules; consequences must always be considered in determining what is right. The ends (considered in totality, obviously) justify the means, or as Eliezer put it, "Shouldness flows backwards". This description may be a bit too inclusive, but i...