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.