If using Ubuntu natty or newer:

sudo apt-get install git-annex

Otherwise, see manual installation instructions.