Existem várias maneiras de conseguir isso. Veja esta resposta para mais detalhes. Adicionar @reboot xbindkeys
ao seu crontab funcionaria, mas aparentemente só funciona quando a máquina é reinicializada quando não está fria.
sudo echo '@reboot xbindkeys' >> /etc/crontab
Isso adicionará a linha aos seus trabalhos agendados, mas normalmente eu chamo o script adicionando-o em uma linha para /etc/init.d/rc.local
, embora eu goste da sugestão de Riccardo de adicioná-lo ao ~ / .gnomerc.