Brushless pump messing up DC power supply?

I was looking also at this image from Wikipedia, which shows decoupling/bypassing as something any type can be used for:

Then if that is what it shows quite simply it is wrong and needs correcting.

Have you read this:- http://www.thebox.myzen.co.uk/Tutorial/De-coupling.html it tells you about self resonance, the point where a capacitor stops looking like a capacitor and starts looking like an inductor and so stops filtering out the interference.

I still have not much of an idea really what I should be filtering exactly - what frequency/voltage/etc

You are doing two things:-

  1. You are lowering the source impedance of the voltage input to the regulator. The motors will have the effect of raising this source impedance.

  2. You are trying to remove very short spikes of under and over voltage caused by the motor. Because they are short then they are a very high frequency.