How do I bind to Shift+{Left,Right} in tmux?

Try this (as a partial example):

bind -n S-Right next-window
bind -n S-Left previous-window

That should be enough to make it easy to get the other 2 settings working too. It works on my tmux installation (1.4) but YMMV.

You can also use the meta key (option on Macs, alt on PCs):

bind-key -n M-Right next-window
bind-key -n M-Left previous-window 

If you're using Terminal.app in OS X you need to enable the use of the option key in the Preferences for that to work. (As far as I remember it works by default in iTerm, but if not it can definitely be enabled.)