Não consegui ver na lista mostrada enquanto escrevia esta pergunta, mas depois vi uma pergunta semelhante e a resposta que estava procurando na lista de perguntas relacionadas à direita:
Como você pode alterar programaticamente um ícone do arquivo?
Parece basicamente que o comando para isso é:
gvfs-set-attribute -t string /path/to/your/file metadata::custom-icon file:///path/to/your/icon.png
Notas:
1. Isso não parece funcionar para os scripts Nautilus nas versões do Ubuntu antes do 12.10.
2. Isso não parece funcionar para os scripts do Nautilus ao executar o Nautilus como root.