Well, I've quite frequently seen queries in rows of 3 elements: a list box with the columns in your db (or plain english names for them), another list box of operators (=, >, <, >=, <=, contains, etc.), and then a text box for the search value.
At the end of each row, you have a button which will allow the user to add another row to the query. I think where I've seen it used, there's an implied AND between the rows. You run into permutation problems with nesting if you offer an OR option between rows.
HTH--I guess it's stating the obvious, but I thought I'd let you know--this seems a fairly common way of doing things. My company organises its search forms this way.