Revision 6818dac5-cdb3-41f0-8bbe-a6a1cc9617a4 - Code Golf Stack Exchange

###Ruby, <del>104</del> 92 characters###

Saved quite a few characters thanks to @Chron

<!-- language: lang-ruby -->

 f=->(s){m=[*?a..?z];l=m.map{|x|[-s.downcase.count(x),x]};s.tr(m*'', l.sort.transpose[1]*'')}

[Online Version][1] here. Sorting of characters with the same count is not defined, as mentioned in another answer. With the input "asdf", each answer has another output so far.

In other words: all answers have the same behaviour (thus represent a decodable encoding) when the input contains the whole alphabet with each letter having a unique count.

 [1]: http://ideone.com/q3MlPm