You can sort by more than one column using one query.
SELECT something FROM table WHERE conditions ORDER BY col1, col2, col3;
All you'd need to do is check each checkbox to see if it was checked and build a string (say called $sort) containing each checked option with commas delimiting.
The results of my example query would be sorted first by col1, then col2, then col3.
However, using checkboxes you will not be able to specify which the user would like to sort by first. For this I'd suggest a set of drop down menus, but if you have lots of sort options that could be tedious for you and the user.
--kinadian