Heavy-ion collisions at BNL’s Relativistic Heavy-Ion Collider (RHIC) and CERN’s Large Hadron Collider (LHC) provide strong evidence for the formation of a quark-gluon plasma, with temperatures extracted from relativistic viscous hydrodynamic simulations shown to be well above the transition temperature from hadron matter. How the strongly correlated quark-gluon matter forms in a heavy-ion collision, its properties off-equilibrium, and the thermalization process in the plasma, are outstanding problems in QCD. We review here the theoretical progress in this field in weak coupling QCD effective field theories and in strong coupling holographic approaches based on gauge-gravity duality. We outline the interdisciplinary connections of different stages of the thermalization process to non-equilibrium dynamics in other systems across energy scales ranging from inflationary cosmology, to strong field QED, to ultracold atomic gases, with emphasis on the universal dynamics of non-thermal and of hydrodynamic attractors. We survey measurements in heavy-ion collisions that are sensitive to the early non-equilibrium stages of the collision and discuss the potential for future measurements. We summarize the current state-of-the art in thermalization studies and identify promising avenues for further progress.