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 ... ];