The basic idea is that each checkbox will need an onChange attribute which calls a function and you'll need to define a javascript function which uses the XMLHttpRequest object:
<script type="text/javascript">
function doQuery(cbox) {
// your AJAX function here
}
</script>
<input type="checkbox" name="myCheckbox" value="foobar" onChange="doQuery(this);">
AJAX stands for "Asynchronous Javascript and XML" and the basic idea is that Javascript lets your browser make additional requests the server without reloading your entire page by using the XMLHttpRequestObject. Try googling PHP AJAX or some similiar for more info.