If your Linux distribution does not have git-annex packaged up for you, you can either build it fromscratch, or you can use a handy prebuilt tarball.
This tarball should work on most Linux systems. It does not depend on anything except for glibc.
Warning: This is a last resort. Most Linux users should instead install git-annex from their distribution of choice.