What caused this noise in these servo signals and how do I properly describe the solution?
Here is what I came up with:

We know that long wires have some resistance R, some inductance L, and some capacitance with respect to another conductor, C. But the issue is, how to distribute these? 

I decided to take R=1 ohm. L and C would be very small. First I created those three wires from your diagram. Signal A, Signal B and GND wire, respectively. Under steady conditions, I assumed servo signals would be drawing 5mA, so, 1000R internal resistance. (I know, I know, this is just an assumption.)



So first, I noticed a possible LC ringing: 





So I put this circuit up (in LTSpice) and ringing was observed.



What I also observed was this: 



So I created another circuit to get L coupling effect and hoped that superimposing both results would give me the correct answer.

L coupling effect on signal A recreated:



Which I think kinda explains what you saw. Now, I superimposed both results to get this:







I wasn't able to really re-create your results of course because I think there are much more parameters than what I've used. But I think the last result seems quite like your observations.

Now for your capacitors: 

I think you added just the right amount to stop ringing and coupling.



Another type of cap:



Please note that capacitance is as important as the internal resistance (and other characteristics) of the capacitor you added. By adding that capacitor, you have also added a high resistance between signal line A and B.

Oh and I forgot to add: when using an osilloscope, the probes will get different results sometimes because, they are themselves, also transmission lines.