I typically use xbindkeys, since the "key combination" grabbers in the GUIs don't always work with the windows keys. You just compile/install xbindkeys, set it to launch on boot, and then put this in ~/.xbindkeysrc:
You can swap out "terminal" with whatever terminal emulator you like (gnome-terminal, konsole, whatever).
I set up all of my Linux machines so that the left windows key opens the terminal. Super convenient.