Lo unico que tu debes de hacer a la hora de buscar es darle preferencia a una búsqueda u otra.
Si no te he entendido mal lo que tu quieres hacer es buscar por categoría si el nombre está vacío sería algo así:
Código PHP:
if (!empty($_POST['nombre'])) {
$consulta = "SELECT * FROM clientes WHERE nombre='".$_POST['nombre']."'";
}else if (!empty($_POST['categoria')) {
$consulta = "SELECT * FROM clientes WHERE categoria='".$_POST['categoria']."'";
}
//Aquí realizariamos la consulta a la bd con mysql_query($consulta);