How can I use AJAX with check-box categories?

You’ll need to hook into the “onchange” event of javascript. When using jquery, it’s as simple as $('<the selector string>').change(function(){});

When ever the values are changed, you’ll do an AJAX request to the server with the new parameters & populate the output screen with the new result. For the server-side, you’ll check the parameters, do some validations & send the response after reading the data from the database.

This codex article will help http://codex.wordpress.org/AJAX_in_Plugins