Make sure you have the standard build tools
apt-get install build-essential
Download OpenJDK
wget http://www.java.net/download/openjdk/jdk7u40/promoted/b43/openjdk-7u40-fcs-src-b43-26_aug_2013.zip
Unzip OpenJDK and change to hsdis folder
unzip openjdk-7u40-fcs-src-b43-26_aug_2013.zip
cd openjdk/hotspot/src/share/tools/hsdis
Download GNU binutils and un-tar
wget http://ftp.heanet.ie/mirrors/gnu/binutils/binutils-2.23.2.tar.gz
tar -xzf binutils-2.23.2.tar.gz
Make the binary
make BINUTILS=binutils-2.23.2
Copy the hsdis binary to your JRE/lib/amd64/server folder
cp build/linux-amd64/hsdis-amd64.so ~/java/jre/lib/amd64/server

Updated for JDK8

wget http://www.java.net/download/openjdk/jdk8/promoted/b132/openjdk-8-src-b132-03_mar_2014.zip
unzip openjdk-8-src-b132-03_mar_2014.zip
cd openjdk/hotspot/src/share/tools/hsdis
wget http://ftp.heanet.ie/mirrors/gnu/binutils/binutils-2.23.2.tar.gz
tar -xzf binutils-2.23.2.tar.gz
# may be needed on Debian if you have multiarch installed
sudo apt-get install libgmp-dev libmpfr-dev libmpc-dev g++-multilib
make BINUTILS=binutils-2.23.2 ARCH=amd64
cp build/linux-amd64/hsdis-amd64.so ~/java8/jre/lib/amd64/server