We present a comprehensive ab initio investigation on Mg$_3$Bi$_2$, a promising Mg-ion battery anode material with high rate capacity. Through combined DFT (PBE, HSE06) and $G_0W_0$ electronic structure calculations, we find that Mg$_3$Bi$_2$ is likely to be a small band gap semiconductor. DFT-based defect formation energies indicate that Mg vacancies are likely to form in this material, with relativistic spin-orbit coupling significantly lowering the defect formation energies. We show that a transition state searching methodology based on the hybrid eigenvector-following approach can be used effectively to search for the transition states in cases where full spin-orbit coupling is included. Mg migration barriers found through this hybrid eigenvector-following approach indicate that spin-orbit coupling also lowers the migration barrier, decreasing it to a value of 0.34 eV with spin-orbit coupling. Finally, recent experimental results on Mg diffusion are compared to the DFT results and show good agreement. This work demonstrates that vacancy defects and the inclusion of relativistic spin-orbit coupling in the calculations have a profound effect in Mg diffusion in this material. It also sheds light on the importance of relativistic spin-orbit coupling in studying similar battery systems where heavy elements play a crucial role.