The most fundamental limitations of a muon-spin relaxation experiment can be the lack of knowledge of the implantation site of the muon and the uncertainty about the muon's perturbation of its host. Here we review some of the work done on the 'muon site problem' in the solid state and highlight some recent applications of electronic structure calculations that have successfully characterized the quantum states of muons in a number of insulating compounds containing fluorine, in a number of pnictide superconductors, and in ZnO.