Sue noted:
...Tony Clark is apparently an Australian artist and a friend of Nick's and the painting is a representation of the Garden of Gethsemane. This is what Nick says about the cover art in The Witness:

"I asked him to come up with a painting that counter-balanced the bleak snow scene of the apocryphal Murder Ballads - the other release that I see as living outside the Bad Seeds' canon. Three days later, Tony brought an extraordinary triptych of six crippled olive trees blasted by bloody red light to my home and it was agreed that this very beautiful, very powerful painting would become the sleeve of the cd."

I agree it's a strong and beautiful piece of work, which is probably best appreciated in its original form rather than reduced onto a little cd sleeve. (The promo prints of the vinyl sleeve which record shops have been giving away are quite nice for the office wall, though!)