How can I use my table for Views 3 sort criteria? I am trying to create a special sort criterium.
I have a table with 2 cols: nid, and count.

How can I use this table to sort the view by count?
You can let Views know about your data using hook_views_data.

The function documentation itself contains all the information you need to use the data for sorting and other Views functions, so I'm not repeating them here.