How should I be thinking about phonons?

You are correct that phonons are quantized sound; sound because they require coherent vibrations. Phonons correspond to the vibrational modes of the unit cells of the crystal. The lowest order mode is when they all move together, which is similar to sound, and are called the acoustic mode; all higher order modes are called optical modes.

Phonons are similar to photons in terms of spin, and Planck's relation, but they require a medium (the crystal), and crystal momentum is not always conserved; crystal momentum can carry real momentum, but doesn't always follow the same rules.

As phonons lose their coherence they add to the thermal energy of the crystal; their lifetimes depend upon the material. Phonons may be absorbed or emitted from excited states; they must be taken into account in many condensed matter systems.

So where are the phonons located? They are essentially located everywhere within the crystal, though they may have specific crystal directions based on the mode.

Phonons can be created by any excitation of the crystal: electric, optical, mechanical. And yes, phonons can interact with electrons; electron-phonon scattering can be an important process.

But it is said the phonons in a crystal are the various vibrational modes of the atoms, but because the centre of mass of the oscillating atoms does not move the k vector of the phonon (crystal momentum) is not a real momentum.

This is not the reason why we say that phonons carry quasimomentum instead of momentum. The actual, physical momentum of a single oscillating ion indeed has nothing to do with the momentum carried by the phonon.

Phonons are longitudinal waves supported by the collective vibrations of the ions constituting a crystalline lattice. In this respect, we can associate them a wavelenght $\lambda$. It is thus tempting to give them a wavevector $\vec{k} = \frac{2 \pi}{\lambda} \vec{u}$ with $\vec{u}$ the direction of the deformation. The quantity $\hbar \vec{k}$ is then called the quasimomentum of the phonon.

However, this momentum is not an actual physical momentum because it does not obey the same conservation rules associated with momentum of usual particles such as photons or electrons. This comes from the fact that the lattice breaks translation symmetry : the medium in which the phonons propagate is a discrete lattice, on the opposite of, for instance, the vacuum in which propagates photons which is continuous. Or if you wish, the "wave" describing the phonons is only defined at a discrete number of points in space : the ions constituting the lattice. Because of the discrete nature of the lattice, there can be different wavelenghts that describe the same physical oscillation, as it is illustrated in this picture. This is the reason why the wavevector of phonons is only defined up to a integer times of the reciprocal vector of the lattice.

Concerning you second question, yes electrons and phonons can interact, it is just that the conservation rules for momentum will be slighly adapted to account for the different nature of the quasimomentum of phonons. Electron-phonon scattering is a major cause of resistivity in metals, and electron-electron interaction via virtual phonon exchange is the microscopical mechanism responsible for superconductivity in many materials.

To awnser your comment, yes phonons are collective vibrations of all the atoms constituting the lattice : you can think of them as some normal modes, just as the normal modes of a vibrating guitar string. An intuitive picture to think of electron-phonon interaction is the following : phonons creates periodic displacements of the lattice, they can thus bring atoms closer or farther apart from eachother in different regions of the lattice. This creates inhomogenities of charge (because the constituents of the lattice are actually ions, and not atoms) ; the electrons being charged particles, they can scatter off these inhomogenities. In the context of superconductivity, there is also an intuitive way of thinking of the Cooper pair formation by electron-phonon interaction : when an electron propagates throught the lattice, it attracts positive ions because of Coulomb interaction. This leaves behind him a trail of positive charge density that can in turn attract another electrons. This creates an effective retarded attractive interaction between the electrons which creates the Cooper pair.