In our everyday world, we typically interact with only three states of matter, solid, liquid, and gas, and occasionally a fourth, plasma (flames, lightning, static). Those first four are actually pretty uncommon in the the universe (plasma is currently the most common state of matter), we on Earth are in a special place that is neither too hot or too cold, so we are witness to these states of matter that occupy the middle of a spectrum of matter states, a Goldilocks environment.
States of matter are closely related to temperature, or more appropriately, energy density. The amount of energy stored in a particular space, whether measured by volume or by mass, defines the energy density. Very little energy in a given space, low energy density, can be thought of as "cold", while lots of energy in a given space, high energy density, can be thought of as "hot". Solids, liquids, and gases are "warm" states of matter, but there are very "cold" states of matter, and very "hot" states of matter as well.
Low Energy Density States
Some of the low energy density states are relevant at extremely cold temperatures. They can be produced in the lab, but it is unlikely that they appear anywhere in nature, anywhere in the universe. Scientist are experimenting with these low energy density states to further understand the behavior of matter and energy. The quantum Hall state is the coldest, seen very near absolute zero. The Bose-Einstein condensate is where bosons (i.e. particles that glue mass carrying matter together, photons - light particles - are an example) can be collapsed together to occupy the same quantum state, effectively becoming a single particle (weird!). A Fermionic condensate is similar, but with mass carrying fermion particles (i.e. quarks and leptons) can occupy the same quantum, but only two at a time.
A superfluid is a cryogenic fluid (super cold), that is frictionless. It can "defy" gravity by flowing up surfaces - spreading out as much as possible. Supersolids are like superfluids in that they are frictionless, but maintain a solid shape.
This list runs from coldest to warm:
Quantum Hall
Bose-Einstein condensate
Fermionic condensate
Superfluid
Supersolid
Solid
Liquid
Gas
Supercritical fluid
High Energy Density States
Aside from plasma, most of the states on this list are relevant at extremely high temperatures. Degenerate matter can be found in the cores of very dense stars, such as white dwarfs (our Sun is merely a big ball of plasma). Quark-gluon plasma can be made in some particle accelerators, while weakly symmetric matter and strongly symmetric matter were around only in a brief period of time following the Big Bang.
This list runs from warm to hottest:
Plasma
Degenerate matter
Quark-gluon plasma
Weakly symmetric matter
Strongly symmetric matter