Using the Android Visualizer class (http://developer.android.com/reference/android/media/audiofx/Visualizer.html), we can retrieve part of the audio data that is currently playing, at a specified sample rate. You can choose to capture data as waveform and/or frequency data:

The data is limited to 8 bits, so it's not useful for playback but is sufficient for visualizations. You can specify the sampling rate, although it must be a power of two.

Armed with this knowledge, we'll now go ahead and begin implementing an architecture that captures audio data and makes it available to visualization renderers that you can build.