this is unfortunately not exactly possible like you want it, probably.
Have you noticed the already existing "Search" functionality above a table which will search "live" in the table and only show table rows that match the search terms?
That probably comes closest to what you need.
Additionally, you could take a look at http://wordpress.org/support/topic/plugin-wp-table-reloaded-main-search-to-pass-keyword-to-datatables-filtering-search, which can automatically initialize that search from above (with a value from your sidebar search form).
A solution that works on the server side is not really possible, but you could check out the Filtering Extension from my website (http://tobias.baethge.com/2010/03/extension-6-showing-only-rows-that-match-a-filter/). This however only allows searching for exact cell contents, so that is not really helpful for your visitors, I guess.
So, summing up, all available ideas will require some custom programming from you. If they don't really satisfy your needs, you will likely have to look into a custom PHP/mySQL solution for your table, which you would then have to use instead of WP-Table Reloaded.