projectM is the Linux equivalent of the MilkDrop visualisation plugin for Winamp, and is compatible with the libvisual engine that Amarok uses for visualisations.
It'll be packaged with the next version of Ubuntu (Hardy) but in the meantime you can install libprojectm1, libvisual-projectm and libprojectm1-data from Debian's lenny repository. Then restart Amarok, and in the visualisations menu choose projectM.
It takes a few seconds to start cycling through the visualisations; right-click on the window or press F11 to switch to full-screen mode; maximise the window before full-screening for full effect; presets are in /usr/share/projectM, configuration options are in ~/.projectM.