  Integrable Killing tensors are used to classify orthogonal coordinates in
which the classical Hamilton-Jacobi equation can be solved by a separation of
variables. We completely solve the Nijenhuis integrability conditions for
Killing tensors on the sphere $S^3$ and give a set of isometry invariants for
the integrability of a Killing tensor. We describe explicitly the space of
solutions as well as its quotient under isometries as projective varieties and
interpret their algebro-geometric properties in terms of Killing tensors.
Furthermore, we identify all St\"ackel systems in these varieties. This allows
us to recover the known list of separation coordinates on $S^3$ in a simple and
purely algebraic way. In particular, we prove that their moduli space is
homeomorphic to the associahedron $K_4$.
