Add sidebar site wide

How easy is it to add a sidebar to a theme?
I am using, and prefer, the Alto theme and would like to have a small sidebar that displays all the tags. I would prefer this to be viewed site wide.
Can someone assist me with this?

If not possible with the Alto theme, can someone recommend a good theme that has the tags in a sidebar?