In this paper, we extend the work of Günther-Hanssen (2020) in applying the INTERNODES method to problems in contact mechanics. In an initial work on this topic, Günther-Hanssen showed that the INTERNODES method could be successfully applied but also revealed several challenges in efficiently solving iteratively the linear systems arising from the method. In this work, we investigate preconditioning techniques for such linear systems. The highly efficient Liu-Woodbury outer-inner preconditioners we propose achieve very fast convergence and to a great extent independent of the mesh size. Our paper is structured as follows: In Section 2 we recall the INTERNODES matrix derived by Günther-Hanssen in the specific context of contact mechanics. We discuss some of its properties and prove a few theoretical results. In Section 3, we begin by motivating the choice of solver for the linear system. We then discuss theoretical aspects relating to preconditioning techniques and later propose our first preconditioner. In the last part of this section we show how it leads to a new linear system for which we propose a second preconditioner. Finally, in Section 4, we conduct a few numerical experiments supporting the theoretical results.