In recent years there have been several theoretical and experimental investigations concerned with the detailed structure of the acceptor states in Mg-doped GaN. Thus, the shallow effective-mass-like acceptor has been attributed to simple substitutional Mg at Ga sites in unstrained regions of the material, while earlier suggestions that the Mg is associated with H appear to have been discounted by more recent studies. Deeper acceptor states have also been attributed to simple substitutional Mg, but in strained regions. The present paper makes use of the extensive data available from electron spin resonance and optically detected magnetic resonance to confirm these assignments and to highlight further the crucial role played by strain in influencing the detailed nature of the acceptor states. In particular, the neutral deep acceptor states are found to be formed by localization of the holes in p-like orbits on N atoms that lie in the basal plane, rather than along the c axis, relative to the Mg dopant.