I have heard several levels of formality of this phrase, said to me when I'm leaving my schools, and said to other people who leave before me, as well:
お疲れ
お疲れさん
お疲れ様
お疲れ様です
お疲れ様でした
Be careful with the first two forms in the list, as they are more informal, and should only be used with colleagues you feel close to, or people below you in the pecking order where you work.
Aside from the levels of politeness, there is little difference between these. The difference between です form and でした is basically just verb tense differentiation:
お疲れ様です = thanks for working hard (today)
お疲れ様でした = thanks for all the hard work you did (today)
and yes, you can say お疲れ様 to your superiors as they leave for the day.
One difference between the two is that お疲れ様でした is said to people who are leaving, by people who are still working, and it conveys a slight sense of envy because the speaker still has work to do.
*edit: I don't understand the downvotes, if it's my "ing" vs "ed" interpretation, is there a better way to parse the difference?