OK, I have figured out a solution. Not as elegant as I was hoping for, but it works. If you can think of a more elegant solution, then I will still award the answer to you.

String categoryOne;
String categoryTwo;

if(userSelectedACategory){
    categoryOne = categoryTwo = userSelection;
}
else{
    categoryOne = '%';//for all categories
    categoryTwo = null;//for records not set to a category
}
[SELECT ID FROM CategoryName__c WHERE (CategoryName__c = :categoryOne OR CategoryName__c = :categoryTwo) AND ... ];

OK, I have figured out a solution. Not as elegant as I was hoping for, but it works. If you can think of a more elegant solution, then I will still award the answer to you.

String categoryOne;
String categoryTwo;

if(userSelectedACategory){
    categoryOne = categoryTwo = userSelection;
}
else{
    categoryOne = '%';//for all categories
    categoryTwo = null;//for records not set to a category
}
[SELECT ID FROM CategoryName__c WHERE (CategoryName__c = :categoryOne OR CategoryName__c = :categoryTwo) AND ... ];

Note, it is possible to extend this idea to dates and ranges of dates.