Here is a working example for one column at a time. I'm working on getting this working for several columns as well: http://jsfiddle.net/mwB37/20/
Since you're asking for a complete plugin with a UI and everything, including relevant code on SO is kinda difficult. But here are the key excerpts that defines my thinking and the concept:
// fetching the column index
var columnIndex = th.index();
// then fetching the corresponding TDs (use for-loop when thousands of elements)
var tds = th.closest('table')
.find('tbody td:nth-child(' + (columnIndex+1) + ')');
// distinctively selecting the unique text values in those columns
var checks = $.unique(tds.map(function() {
return $(this).text();
}).get());
// the most basic way possible of filtering
// (should be extended into an OR query of all current column filters)
if (index != -1 || arr.length == 0)
td.parent('tr').show();
else
td.parent('tr').hide();
If you want something already finished instead, this is such a plugin: PicNet Table Filter
There is also a filtering plugin available for the jQuery DataTables plugin, although sorting is obviously the main focus of that one.