How do I structure this lisp macro?

Since you didn't say what you tried I don't know what you did wrong, but I guess you probably tried to replace the individual cases inside the CASE with macro calls? That doesn't work because the outer macro (CASE) is expanded before the inner ones, so an inner macro can't be used to generate syntax for an outer macro (unless the outer macro is specifically written to allow that, which is not the case here).

So the solution is to write a macro that generates the whole CASE for you. Something like:

(macrolet ((ops-case (op-sym (&rest ops))
             `(case ,op-sym
                ,@(loop for op in ops
                        collect `((,op) (,op (evaluate-boolean left bindings)
                                             (evaluate-boolean right bindings))))
                (otherwise (error "Invalid operator ~A" ,op-sym)))))
  (ops-case op (and or nand nor xor impl equ)))

Although I'm not convinced this is really a good idea. One off macros like this tend to make your code harder to understand, and this doesn't significantly shorten the code either. Usually you would want to use macros to abstract patterns that appear multiple times in your code.

A more generic approach might be something like this:

(defmacro ecase-template (keyform template &body cases)
  `(ecase ,keyform
     ,@(loop for case in cases
             collect (sublis `((_ . ,case)) template))))

This generates a case expression by substituting underscores in a tempate with a value from the case. For example:

CL-USER> (macroexpand-1 '(ecase-template op
                             ((_) (_ (evaluate-boolean left bindings)
                                     (evaluate-boolean right bindings)))
                           and or nand nor xor impl equ))
(ECASE OP
  ((AND)
   (AND (EVALUATE-BOOLEAN LEFT BINDINGS) (EVALUATE-BOOLEAN RIGHT BINDINGS)))
  ((OR)
   (OR (EVALUATE-BOOLEAN LEFT BINDINGS) (EVALUATE-BOOLEAN RIGHT BINDINGS)))
  ((NAND)
   (NAND (EVALUATE-BOOLEAN LEFT BINDINGS) (EVALUATE-BOOLEAN RIGHT BINDINGS)))
  ((NOR)
   (NOR (EVALUATE-BOOLEAN LEFT BINDINGS) (EVALUATE-BOOLEAN RIGHT BINDINGS)))
  ((XOR)
   (XOR (EVALUATE-BOOLEAN LEFT BINDINGS) (EVALUATE-BOOLEAN RIGHT BINDINGS)))
  ((IMPL)
   (IMPL (EVALUATE-BOOLEAN LEFT BINDINGS) (EVALUATE-BOOLEAN RIGHT BINDINGS)))
  ((EQU)
   (EQU (EVALUATE-BOOLEAN LEFT BINDINGS) (EVALUATE-BOOLEAN RIGHT BINDINGS))))

This might not be quite what you are after, but CLOS is just fantastic for this kind of dispatch-on-symbol evaluation.

Here is a (very minimally-tested) implementation of your evaluator using a pair of generic functions (which are, of course, really eval and apply for your little language) together with a macro which lets you define 'direct' methods for the apply generic function. A 'direct' method is one which translates trivially to a form involving an operator with the same name in the subtrate language (this basically covers all the big nested case in your code).

(There are some cases where it works slightly differently than your code: for instance once it's found a variable binding it just punts back into the evaluator with its value, rather than having any additional special case cleverness.)

(defgeneric evaluate-boolean (expression bindings)
  (:documentation
   "Evaluates the boolean expression. Returns t or nil

expression := variable 
            | constant 
            | '(' operator expression expression ')' 
            | '(' not expression ')'
            .
constant := 'true' | 'fail' .
variable := symbol .
operator := 'and' | 'or' | 'nand' | 'nor' | 'xor' | 'impl' | 'equ' .

bindings is a list of pairs (variable . constant)
")
  (:method ((expression (eql 'true)) bindings)
   (declare (ignore bindings))
   t)
  (:method ((expression (eql 'false)) bindings)
   (declare (ignore bindings))
   nil)
  (:method ((expression symbol) bindings)
   (let ((binding (assoc expression bindings)))
     (if binding
         (evaluate-boolean (cdr binding) bindings)
       (error "no binding for ~A" expression))))
  (:method ((expression cons) bindings)
   (apply-boolean-operator (car expression) (cdr expression) bindings))
  (:method (expression bindings)
   (error "malformed expression ~A" expression)))

(defgeneric apply-boolean-operator (op args bindings)
  (:documentation "apply an operator to some arguments with some bindings")
  (:method (op args bindings)
   (error "unknown operator ~A" op)))

(defmacro define-direct-boolean-operator (op-name arg-names)
  (unless (and (symbolp op-name) (list arg-names) (every #'symbolp arg-names))
    ;; not even worth trying
    (error "mutant boolean operator definition"))
  `(defmethod apply-boolean-operator ((op (eql ',op-name))
                                      args bindings)
     ;; this smells unhygenic but I think it is actually fine
     (let ((la (length args))
           (lr ,(length arg-names)))
       (unless (= la lr)
         (error "~A wanted ~D argument~P but got ~D" op lr lr la)))
     (destructuring-bind ,arg-names args
       (,op-name ,@(mapcar (lambda (a)
                             `(evaluate-boolean ,a bindings))
                           arg-names)))))

(define-direct-boolean-operator not (x))
(define-direct-boolean-operator and (x y))
(define-direct-boolean-operator or (x y))
(define-direct-boolean-operator nand (x y))
(define-direct-boolean-operator xor (x y))
(define-direct-boolean-operator impl (x y))
(define-direct-boolean-operator equ (x y))