If using Ubuntu Oneiric or newer:

sudo apt-get install git-annex

Otherwise, see manual installation instructions.

There is a PPA with a newer version of git-annex in it, maintained by Sergio Rubio. https://launchpad.net/~rubiojr/+archive/git-annex

Warning: The version of git-annex shipped in Ubuntu Oneiric has a bug that prevents upgrades from v1 git-annex repositories. If you need to upgrade such a repository, get a newer version of git-annex.