There are a number of ways to accomplish this. See this answer for more details. Adding @reboot xbindkeys to your crontab would work, but apparently only works when the machine is rebooted not when it comes up cold.
sudo echo '@reboot xbindkeys' >> /etc/crontab
That will add the line to your cron jobs, but typically I call the script by adding it in a line to /etc/init.d/rc.local, though I like Riccardo's suggestion of adding it to ~/.gnomerc.