This has been touched on some at the git-annex page:
http://git-annex.branchable.com/forum/migrate_existing_git_repository_to_git-annex/
My experience was less complicated, I did not need to edit .gitattributes and therefore did not need to do a bunch of rebases on the front end. I also only had one branch.
git filter-branch --tag-name-filter cat --tree-filter 'mkdir -p .git-annex; cp ${MYWORKDIR}/.tmp/* .git-annex/; find . -size +5M -type f -not -ipath \*.git\* -not -ipath \*.temp\* -print0 | parallel -0 -j1 ~/bin/gax; git reset HEAD .git-rewrite; :' -- master
The script that GNU parallel is calling: ~/bin/gax looks like this:
#!/bin/bash
f=$1;
git annex add ${f};
annexdest=$(readlink ${f});
ln -sf ${annexdest#../../} ${f};
The script could be made faster by passing all the files at once (git annex ignores adds for non-existent files), but you would have to do loop over the symlink part to fix them all.
The filter-branch command could also be made faster by first generating the list of files using find, and using that list instead of running find on the working tree every time.