Clique no botão home do painel de controle e digite "aplicativos de inicialização" (sem as aspas) e você poderá abrir o programa Aplicativos de inicialização .
Configurar um programa do Windows para ser executado na inicialização via Wine é tão fácil quanto adicionar um aplicativo de inicialização com um comando assim:
wine "/home/jeffy/.wine/drive_c/Program Files/herp/derp.exe"
Aqui, as aspas são importantes, pois sem elas, os espaços não seriam registrados corretamente como parte do texto no comando.
Obviamente, você terá que colocar o caminho para o seu arquivo .exe em vez do caminho de amostra que eu coloquei, mas isso deve ser um começo. Se não me engano, o Wine vem com uma ferramenta para navegar na sua falsa unidade C, por isso deve ser fácil encontrar o programa que está procurando.