I implemented quite a similar requirement. I'm using Criteria API, because you don't have to use string operations to put you query together, which makes it more stable.
I posted a simple example in this question, how to put a dynamic query together.
In our solution, I didn't allow OR operations, because it makes it very complicated (also UI part) and performance could get bad. But later, we probably implement it as well.
Design decisions need to be made according to your requirements and the complexity of your queries and data structure.
For instance, I made a filter class for each query. The filter class holds predefined fields. This makes it more stable, because you always know which fields could be there, and can put them on certain places into the query. Some fields require subqueries. In our case it is impossible to make it fully generic (this means: that all the information how the query should be built up is stored in the filter). There is specific method for each filter class to turn it into a query. This gives you a lot of flexibility.
My criteria consist of a reference to a field, an operator (enum) and an argument.