It happens because of the cheapest circuit possible, too little bypassing, sometimes too much stress for the components (some parts may be operating around limits), pretty much if you just try to sketch a charging circuit, you get a cheap charger. All those thermal compensation stuff and noise filtering is extra cost and extra brainwork.
Yes, it's bad for devices. Overshoots in particular, but constant significant noise will reduce lifetime of the circuits that are charged with this device. In fact, you never know what will be harmed an what won't.
Removing AC from DC is one of the main purpose of capacitors. You put a capacitor between power line and ground:
First of all, determine noise frequency (estimate). Decade is enough, you only need to understand if it's 100Hz or 1kHz or 10kHz or whatever it is. You could then choose the correct bypass cap which will be best for filtering out the undesired frequencies.
Look at this chart:

Of course, it's only estimate, but it's a good starting point.
You want to have minimum resistance at your noise's frequency, which will mean, that the noise will go through the capacitor to the ground, while the rest of the frequencies stay untouched (not literally, you see the graph, but you get my point). Nothing stops you from using 2-3 caps of very different values (very small one like 1nF, 1uF and some 68uF electrolytic against low frequency noise, this is just an example, but you can give it a try, such a set covers wide spectrum of frequencies to filter out). Of course, since you can measure the noise, I assume you have scope, so you can always just try stuff and see what happens and how much it helps. To put it simple, proper bypassing should make it a lot better.
You can go with cheap disk ceramic caps. Even those ebay sets will do, and they should be just fine at 5V, don't know if they don't explode with 12V+, but 5V no problem.
Another small addition: a 5.1V zener from power line to ground (reversed, anode(+) on the ground side) will ensure you don't have dangerous overshoots, it will clip any voltage above 5.1, but if you bypass it well, you won't really need it (again, the scope should tell you)