Yes definitely ceramic capacitors - you need capacitors with a low impedance at the frequencies of interest, no electrolytic can cut it, ceramic caps at 10uF and 0.1uF are a good start - small series indurctor (it needs a high impedance at the frequencies of interest).
The problem is that capacitors have stray inductance and that inductors have stray capacitance. A key spec to look at is the self-resonant frequency -- your decoupling caps and inductors should have self-resonant freq ABOVE the frequencies of interest - otherwise they behave completely the wrong way round (and act as high-pass filter!!). Since wiring has inductance its vitally important to use good layout to the capacitor(s), otherwise the noise can simply bypass it.
Also be aware that scope-probes can pick up noise that's not actually in your circuit - its picking up capacitively and/or inductive coupled noise directly from the power supply, so make sure to measure the noise at the load, away from the supply.