The computational study of electron-phonon interactions in bulk materials requires a very fine sampling of electron and phonon momenta inside the first Brillouin zone. Various interpolation techniques have been developed over the past decade to improve computational performance. We expand on these developments by presenting an ab-inito approach for describing electron-phonon interactions within the projector augmented-wave (PAW) method. Our approach utilizes Wannier-interpolation to efficiently construct the required matrix elements at arbitrary points in the first Brillouin zone. Additionally, the finite difference method is used inside a supercell to evaluate the involved derivatives, thereby enabling the use of the widest possible range of density functionals. The formalism is derived from the theoretical framework of Allen, Heine and Cardona using second-order perturbation theory. Physical quantities of interest can be expressed as a sum of matrix elements involving only the PAW Hamiltonian, the PAW overlap, derivatives thereof and the unperturbed electronic pseudo wave functions. A quantity analogous to the electron-phonon matrix element can be defined within the PAW method. This is used to calculate, among other quantities, the temperature-dependent renormalization of the electronic band structure. Future extensions to the method pertain the inclusion of polar interactions, an automatic Wannierization process and a field-theoretical formulation.