$E$ is a holomorphic vector bundle if and only if there is a Dolbeault operator $\bar{\partial}_E$

There is a proof in section 2.2 of The geometry of four-manifolds, by Donaldson and Kronheimer. They point out the similarities between the proofs of the integrability theorems for Dolbeault operators and for flat connections.

(While it's possible to prove this integrability theorem by quoting Newlander-Nirenberg, the PDE problem that underlies it is considerably easier to solve than the N-N problem, because the bundle is decoupled from the coordinates on the base.)

Maybe R.O. Wells' book ?

http://www.amazon.com/Differential-Analysis-Manifolds-Graduate-Mathematics/dp/0387738916

Sorry I'm not in the office so I can't check.

I don't think it's particularly difficult. Certainly if the bundle is holomorphic you can construct the Dolbeault operator by just acting on the components of a section written as a linear combination of holomorphic sections. This patches to give a global Dolbeault operator because the clutching functions are holomorphic. To go the other way you need an integrability theorem such as Newlander-Nirenberg to show there are enough sections in the kernel of the Dolbeault operator to span the fibre of the bundle and trivialise it locally.

A. Moroianu gives a detailed proof on pp. 72-74 of his Lectures on Kähler geometry (Theorem 9.2), available on the internet. (The preprint has it as Theorem 3.2.)

He attributes that proof to S. Kobayashi, Differential geometry of complex vector bundles. I guess he means Proposition I.3.7 there, which Kobayashi couches in a different language involving connections.

P.S. Note that Moroianu gives himself a whole complex of operators $\bar\partial_E:\Omega^{p,q}(E)\to\Omega^{p,q+1}(E)$, and Donaldson-Kronheimer at least the $(0,q)$ ones, plus Leibniz. I'm not 100% clear that just the $(0,0)$ one plus Leibniz suffice to determine everything, as the question seems to imply.