Spectrum inference, also known as spectrum prediction in the literature, is a promising technique of inferring the occupied/free state of radio spectrum from already known/measured spectrum occupancy statistics by effectively exploiting the inherent correlations among them. In the past few years, spectrum inference has gained increasing attention owing to its wide applications in cognitive radio networks (CRNs), ranging from adaptive spectrum sensing, and predictive spectrum mobility, to dynamic spectrum access and smart topology control, to name just a few. In this paper, we provide a comprehensive survey and tutorial on the recent advances in spectrum inference. Specifically, we first present the preliminaries of spectrum inference, including the sources of spectrum occupancy statistics, the models of spectrum usage, and characterize the predictability of spectrum state evolution. By introducing the taxonomy of spectrum inference from a time-frequency-space perspective, we offer an in-depth tutorial on the existing algorithms. Furthermore, we provide a comparative analysis of various spectrum inference algorithms and discuss the metrics of evaluating the efficiency of spectrum inference. We also portray the various potential applications of spectrum inference in CRNs and beyond, with an outlook to the fifth-generation mobile communications and next generation high frequency communications systems. Last but not least, we highlight the critical research challenges and open issues ahead.