Install the appropriate libraries via apt-get, libao0 and libmad0, (they may be in devel, so you install at your own risk) then run the executable from the X Terminal Emulator from wherever you downloaded it to.
I'm looking into packaging it, but pianobar uses CMake, so I'm having trouble with dpkg-buildpackage.