TortoiseHG previously worked on 12.10, but after today's reinstall, it simply doesn't show up, not even with the thg command.
I managed to install it rather easily by using the tortoisehg ppa:
sudo add-apt-repository -y ppa:tortoisehg-ppa/releases
sudo apt-get update
sudo apt-get install mercurial tortoisehg
Note: @piwi's method works too.