Debian/Ubuntu: apt-get install mercurial

Windows/MacOSX: mercurial.berkwood.com

(there's also this page which bundles Mercurial with some additional packages, i.e. a merge tool, an ssh tool. Did anyone try that?)

see also: Mercurial Wiki