Você pode usar sed :
sed -i 's/^/your_string /' your_file
Graças aos comentários de Stephane e Marco, note que a opção -i não é POSIX. Uma maneira POSIX de fazer o acima seria
sed 's/^/your_string /' your_file > tmp_copy && mv tmp_copy your_file
ou perl :
perl -pi -e 's/^/your_string /' your_file
Explicação
Ambos os comandos executam uma substituição de regex, substituindo o início de uma linha ( ^ ) pela sua string desejada. A opção -i em ambos os comandos garante que o arquivo seja editado (ou seja, as alterações são refletidas no arquivo em vez de impressas no stdout).
sed deve estar disponível em qualquer sistema operacional compatível com POSIX e perl deve estar disponível na maioria dos Unices modernos, exceto talvez para aqueles que passaram pelo esforço de removê-lo.