O redirecionamento ( >> ) é feito pelo shell; seu sudo afeta apenas echo .
Você pode usar esse truque:
echo "something" | sudo tee -a /output/file > /dev/null
Dessa forma, tee anexará o texto ao /output/file com as permissões adequadas.
EDIT (respondendo comentário): tee foi projetado para passar sua entrada e duplicá-la (em geral: multiplicar). Neste caso, uma cópia vai para o arquivo e a outra viaja ao longo do tubo. Como só precisamos do primeiro, redirecionamos a segunda cópia para /dev/null para que não apareça no console. Tudo o que vai para /dev/null desaparece.