The theory of quantum information has emerged as an indispensable tool in the study of many-body, high-energy, and gravitational physics, vastly over-delivering on its initial promises in quantum communications and computation. Significant insight has come from the analysis and quantification of quantum entanglement, a phenomenon that leaves an indelible imprint on the structure of a quantum state. In this thesis, I move beyond entanglement theory to incorporate the theory of distinguishability in many-body and gravitational physics. The notion of distinguishability provides a natural language and unique perspective on the physics of black hole evaporation and thermalization of isolated quantum many-body systems. I first develop tools to evaluate measures of distinguishability in random states and evaluate ``Page curves'' for various relative entropies and fidelities. I then relate these computations and generalize them to gravitational systems, characterizing when and how different black hole microstates in a gravitational model become distinguishable using measurements on their radiation and in what sense information can be recovered, a fine-grained resolution to a version of Hawking's information paradox. I furthermore discuss the role of relative entropy in AdS/CFT and the random tensor networks and quantum error-correcting codes that it is modeled by. Moving away from gravity, I discuss how distinguishability measures characterize the physics of quantum thermalization both in out-of-equilibrium processes and in high-energy eigenstates of non-integrable Hamiltonian systems. Under an ansatz for these high-energy states, I derive the eigenstate thermalization hypothesis in its strongest form. Along with unpublished results, this thesis incorporates lightly edited material from Refs. [106,108,112,183].