What exactly is the "coherence" between waves? I know, by definition, that coherence means that a pair of waves have constant phase difference. What does this mean? 
Does it mean they always have a 360 degrees, or 0 degrees phase difference? Or could they have 40 degrees or any constant phase difference?
In order to have constant phase difference must they have the same wavelength and frequency?
 A: Waves can be coherent and yet not have the same wavelength. It is sufficient that they have the same frequency - because that is sufficient to imply a constant phase difference.
If you make a Michelson interferometer where you split an incoming light beam into two arms, and you send half the light through a column of water and the other half through air, then it is possible to get interference between the beams by adjusting the path lengths (according to the refractive index).
It is worth noting that typically waves do not consist of a single pure frequency, and that there will be some small drift in frequency over time. Because of this, if you split light into two branches but make them come back together after they have covered different path lengths, then the interference pattern they will create (a measure of the coherence) will become less.
For this reason, with "monochromatic" light we sometimes talk of the "coherence length" - a measure of how different the path lengths can be before you lose a significant fraction of the coherence (before the interference pattern starts to fade).  As @wbeaty pointed out, it is more proper to call this the temporal coherence length (how much earlier or later can you look at the beam and find it is still capable of interference) - but since you are measuring time "along the beam", there is a direct relationship between the coherence time and the length along the beam that the light can interfere.
A: Coherence means a constant phase relationship; the phase difference could be anything, such as $\pi$ or $7 \pi / 4$. 
Naively, that means that two waves are coherent if and only if they have the same frequency, which makes the idea of coherence sound silly. However, it actually stands in for a lot of real world effects that can destroy interference. For example:


*

*Light from a fluorescent bulb, which has (roughly) a single frequency, is not coherent. Each atom in the bulb is wiggling independently, so instead of getting one light wave at some frequency, you get a ton of little wavetrains of the same frequency but independent phases, one from each atom.

*Even if you fix the above problem, light can't have a definite frequency. Classically, if you look at an EM wave, it satisfies an uncertainty principle of the form $\Delta \omega \Delta t > 1$ for the same Fourier-transform reasons that the usual uncertainty principle holds. Quantumly, if you're considering photon emission, it satisfies the uncertainty principle $\Delta E \Delta t > \hbar$, which gives you the same thing. Since all light contains a range of frequencies, it is impossible to have exactly the same frequency, and the effect is noticeable after some length scale.


The length scales above are called coherence lengths. Above the coherence length, interference patterns start to fade.
A: Yes, it is exactly so. The same phase difference, wave length and frequency. What is important, but implicit here, is that both waves exist at the same time at the same place. Then they added up and act on a screen or on a probe charge as a sum. Their interference is impossible if they do not act at the same time.
