I think filling the sidebar with the proper tags would be the first to be done since right now the tags do not work. After that i'd do the clickable tags since

I think filling the sidebar with the proper tags would be the first to be done since right now the tags do not work. After that i'd do the clickable tags since it sounds the easiest once you have a tag filter there. Including the tag in the regular search also sounds easy, so that could be done next, then the explicit tags. I'd leave the drop box for after the tag stuff since it sounds the hardest (although there might be some HTML5 element that does it for you and all you need to do is feed it with the values, TBH my webdev knowledge stops somewhere between HTML3 and HTML4 :-P).