Spin-orbit configuration interaction (CI) is formulated in terms of the graphical unitary group approach (GUGA) in combination with relativistic core potential and spin-orbit operators, thus providing an efficient general method for treating the electronic structure of molecules containing heavy atoms. The development of the spin-orbit matrix elements and the implementation of these methods in the COLUMBUS suite of programs are described.