We review the present status in the theoretical and phenomenological understanding of charmonium and bottomonium production in heavy-ion collisions. Starting from an introductory historical perspective, recapitulating the basic notion of "anomalous quarkonium suppression" in heavy-ion collisions, we develop ingredients and concepts aimed at a comprehensive approach to utilize heavy quarkonia as a probe of hot and dense matter. The theoretical discussion encompasses recent lattice QCD computations of quarkonium properties in the Quark-Gluon Plasma, their interpretations based on effective potential models, inelastic rate calculations and insights from the analyses of electromagnetic plasmas. In particular, we emphasize the powerful techniques of thermodynamic Green functions (T-matrices) which provide a rather general framework to implement microscopic quantities into a description of heavy quarkonium suppression and regeneration within a kinetic theory. The theoretical concepts are tested in applications to heavy-ion reactions at SPS, RHIC and LHC. We outline perspectives for future experiments on charmonium and bottomonium production in heavy-ion collisions over a large range in energy (FAIR, RHIC-II and LHC) which are expected to answer key questions in using quarkonium probes of hadronic matter under extreme conditions.