A few things have changed since the top answers were added. They used to work out for me, but not quite anymore, so I have been hacking around for a bit and came up with the following solution for Ubuntu 16.04. For Ubuntu 14.04, see the comment at the bottom of the answer. Apologies if this doesn't work for shared hosting, but it seems like this is the goto answer for wkhtmltopdf installation instructions in general.
# Install dependencies
apt-get install libfontconfig \
zlib1g \
libfreetype6 \
libxrender1 \
libxext6 \
libx11-6
# TEMPORARY FIX! SEE: https://github.com/wkhtmltopdf/wkhtmltopdf/issues/3001
apt-get install libssl1.0.0=1.0.2g-1ubuntu4.8
apt-get install libssl-dev=1.0.2g-1ubuntu4.8
# Download, extract and move binary in place
curl -L -o wkhtmltopdf.tar.xz https://github.com/wkhtmltopdf/wkhtmltopdf/releases/download/0.12.4/wkhtmltox-0.12.4_linux-generic-amd64.tar.xz
tar -xf wkhtmltopdf.tar.xz
mv wkhtmltox/bin/wkhtmltopdf /usr/local/bin/wkhtmltopdf
chmod +x /usr/local/bin/wkhtmltopdf
Test it out:
wkhtmltopdf http://www.google.com google.pdf
You should now have a file named google.pdf in the current working directory.
This approach downloads the binary from the website, meaning that you can use the latest version instead of relying on package managers to be updated.
Note that as of today, my solution includes a temporary fix to this bug. I realize that the solution is really not great, but hopefully it can be removed soon. Be sure to check the status of the linked GitHub issue to see if the fix is still necessary when you read this answer!
For Ubuntu 14.04, you will need to downgrade to a different version of libssl. You can find the versions here. Anyways, be sure to consider the implications of downgrading libssl before doing so on any production server.
I hope this helps someone!