Ruby 58 80

(a=gets.split(/[_\W]+/)).uniq.map{|w|[w,a.count(w)]}.sort_by(&:last).map{|x|p x}

^{Edit: Ok, I was way off. I forgot to sort the words by occurrences. Also, Array#uniq is not an enumerator, but uses a given block to compare elements, so passing puts to it didn't filter out duplicates (not that it says that we should).}

Editing the question, eh? Here's a version sorting in descending order (82 characters):

(a=gets.split(/[_\W]+/)).uniq.map{|w|[w,a.count(w)]}.sort_by{|x|-x[1]}.map{|x|p x}