By far, the easiest one I've used is: http://datatables.net/
Amazingly simple...just make sure if you go the DOM replacement route (IE, building a table and letting DataTables reformat it) then make sure to format your table with and or it won't work. That's about the only gotcha.
There's also support for AJAX, etc. As with all really good pieces of code, it's also VERY easy to turn it all off. You'd be suprised what you might use, though. I started with a "bare" DataTable that only sorted one field and then realized that some of the features were really relevant to what I'm doing. Clients LOVE the new features.
Bonus points to DataTables for full ThemeRoller support....
I've also had ok luck with tablesorter, but it's not nearly as easy, not quite as well documented, and has only ok features.