Debian appears to have removed this plugin from the package but you can compile the scrobbler plugin without any issues.

aptitude install libcurl4-dev audacious-dev

wget http://distfiles.atheme.org/audacious-plugins-2.2.tgz

tar -zxvf audacious-plugins-2.2.tgz

cd audacious-plugins-2.2

./configure --enable-dependency-tracking --disable-esd --disable-pulse --disable-coreaudio --disable-icecast --disable-dockalbumart --disable-altivec --disable-sse2 --disable-mp3 --disable-libmadtest --disable-rocklight --disable-lirc --disable-evdevplug --disable-hotkey --disable-gnomeshortcuts --disable-statusicon --disable-aosd --disable-aosd-xcomp --disable-adplug --disable-vorbis --disable-flacng --disable-libFLACtest --disable-wavpack --disable-aac --disable-sndfile --disable-modplug --disable-ffaudio --disable-jack --disable-sid --disable-oss --disable-oss4 --disable-alsa --disable-amidiplug --disable-amidiplug-alsa --disable-amidiplug-flsyn --disable-amidiplug-dummy --disable-cdaudio --disable-streambrowser --enable-scrobbler --enable-lastfm --disable-neon --disable-mms --disable-mtp_up --disable-bluetooth --disable-paranormal --disable-xspf --disable-xmltest --disable-cue --disable-projectm --disable-projectm-1.0 --disable-filewriter --disable-filewriter_mp3 --disable-filewriter_vorbis --disable-filewriter_flac --disable-bs2b

cd src/scrobbler/

make

make install

cd ../lastfm/

make

make install

Restart audacious and go to General plugins to enable it.