I just did my first addon keybindings yesterday (for OmniStats), and it's pretty well laid out in
AddOn Quick Questions on the wiki how to do it.
Unless there's other ways of doing it, katkat42 is correct in that you have to define your keybindings in advance (in bindings.xml and bindings.lua).