A co-worker recently did this
encapsulate each criteria query in it's own class (specification).
built an expression builder that will spit out the query to the string.
tested that the generated expression string matches the expected expression string.
the expression builder walked the criteria tree in a specification in a recursive fashion to generate the expression string.
that's the general idea, don't have the code with me right now :) sorry.
However, I've found that it's much easier to write db integration tests to test Nh criteria.
Does the criteria really return the data I expect.