Clojure Vars can have thread-local bindings. binding uses these, while with-redefs actually alters the root binding (which is someting like the default value) of the var.
Another difference is that binding only works for :dynamic vars while with-redefs works for all vars.
Examples:
user=> (def ^:dynamic *a* 1)
#'user/*a*
user=> (binding [*a* 2] *a*)
2
user=> (with-redefs [*a* 2] *a*)
2
user=> (binding [*a* 2] (doto (Thread. (fn [] (println "*a* is " *a*))) (.start) (.join)))
*a* is 1
#<Thread Thread[Thread-2,5,]>
user=> (with-redefs [*a* 2] (doto (Thread. (fn [] (println "*a* is " *a*))) (.start) (.join)))
*a* is 2
#<Thread Thread[Thread-3,5,]>
You can use the (undocumented) binding-conveyor-fn to convey thread-local bindings into new threads:
user=> (binding [*a* 2] (doto (Thread. (#'clojure.core/binding-conveyor-fn (fn [] (println "*a* is " *a*)))) (.start) (.join)))
*a* is 2
#<Thread Thread[Thread-5,5,]>