We start by giving an answer that rephrases the Nijenhuis integrability condition
using the foliations, $A,B$, but
the main point here is
to present a more geometric
criterion for integrability, related to complex structures of moduli spaces.
The main claim is that leafwise
holomorphicity of certain natural holonomy induced maps (ie transverse moduli)
give necessary and sufficient conditions for integrability.
We finish with some more speculative questions/answers.
To pick up where Robert Bryant left off,
by Nijenhuis, Newlander--Nirenberg and the
hypotheses
on $A,B,J$, (leafwise complex structures),
our problem reduces to the pair of systems of equations,
$$ (1) P_B^{0,1}(L_{X_i}Y_j)=0, \ (2) {\rm\ likewise\ with\
A,B \ switched}$$
where $L_{X_i}$ is a Lie derivative, (tensored by $C$)
$ X_i,Y_j$ a basis, for $T^{1,0} M$,
$ X_i\in T^{1,0} A$ is a J-holomorphic vector field along $A$, and
likewise for $Y_j$ along $B$, and
$P_A^{0,1}: T^C M \mapsto T^{0,1} A$,
($T^C M=T^{1,0} M \oplus T^{0,1} M $),
are ($A,B, T^{i,j}$ adapted) projections.
So integrability of $J$ is equivalent to formal
vanishing of these projected mixed Lie-bracket terms, and
the general idea here is that this
strongly suggests putting things in terms of
the holonomy of $A$ acting on $B$
(or on $J_{|TB}$).
Likewise, switching
$A,B$ provides the other needed equations.
We want to interpret this system of equations
in terms of
some kind of holomorphicity of {\it holonomy},
along a leaf.
I don't know any references dealing with this specific structure,
but what follows is related to things like holomorphic motions,
and HCMA (homogeneous complex Monge-Ampere equations).
So what we will propose now may have some new aspects, but it is not too far from things
already done in these related areas.
Now we consider more directly the relation of the holonomies of $A$ and $B$ to integrability of $J$.
A (local) leaf $A_x \owns x$ parametrizes a family $B_y, y\in A_x$
of the (local) leaves it intersects, and the foliation $A$ near
$A_x$ induces a map $H:A_x\to {\cal J}$ where ${\cal J}$ is the
space of
complex structures on the (local) leaf $B_x$.
(we just pullback restrictions of $J$ to $B_y$ by
the Holonomy,
ie a flow in $A$).
But ${\cal J}$ itself
has a complex structure,
as in the theory of moduli spaces; it comes from the complex structure induced by $J$
on the Lie algebra of diffeos of $B_x$ (or vector-fields).
Basically, because ${\cal J}$ is a quotient
space of the space (or pseudogroup) of Diffeos of $B_x$.
{\bf Claim}: Given $J$ integrable on $M$,
If $H_A: A_x\to {\cal J}$ is holomorphic for all $x\in U$, an open set,
then
either $A$ or $B$ is transversely holomorphic on $U$.
Conversely, if $B$ is transversely holomorphic on $U$
then $H_A: A_x\to {\cal J}$ is holomorphic on $U$.
This shows that holomorphic $H_A$ is too strong for our purposes, but
a transversely linearized version of the 2nd part of the claim will turn out to be just what we need.
{\bf Proof } of claim:
$H_A$ is a constant map iff $A$ is transversely holomorphic.
If $H_A$ is a non-constant map then since the holonomy of $B$
commutes (by the definition of $H_A$) with the holomorphic maps
$H_A: A_x\to {\cal J}$, the holonomy of $B$ must be itself
holomorphic, proving the first part. Notice that branch points of $H_A$ give
removable singularities for holonomy ($L_Y J_{|A}$) of $B$.
2nd part:
$B$ is a transversely holomorphic foliation by
smooth holomorphic varieties in a ball in $C^N$,
so up to a holomorphic coordinate change, $f$,
it is just a family of parallel n-planes. Also $A_0$ can be taken to be a
k-plane for the same $f$, ($x=0$ here).
Representing leaves of $A$ as graphs over $A_0$ with values in $B_0$
gives the converse.
(Leafwise holomorphicity is the main point, but $H_A$ is even fully holomorphic.) {\bf qed}.
We will weaken the holomorphicity property of $H_A$ by
just using the $J$ induced on the normal bundle of a leaf $NA_x$,
and we now consider holomorphicity of the holonomy pullback
induced on $(NA_x,J)$.
${{\cal J}_{N_xA}}={{\cal J}_N}$ is the homogeneous space, $SL(2n,R)/SL(n,C)$, with its natural complex structure,
ie the
space of
complex structures on the tangent space $T_xB=T_xB_x$.
Consider now
the map $NH:A_x\to {{\cal J}_N}$, namely the restriction of
$H_A$ on the leaf $A_x$ to 1-jets at $x$ of $B_x$.
{\bf Corollary}:
Given $J$ integrable on $M$,
$NH:A_x\to {{\cal J}_N}$ is A-leafwise holomorphic.
{\bf Proof}:
Apply the 2nd part of the claim above, but using a transversely holomorphic foliation
$B'$ transverse to $A_x$. A family of parallel n-planes suffices (working locally). {\bf qed}.
Now we note that there is no discrepancy between pulling-back $J$ from $NA$ instead of $TB$,
(even though $TB$ is not holomorphic along a leaf),
and we will show that the Nijenhuis system above is equivalent to
holomorphicity of $NH$.
Given any $x\in M,A,B,J$ as in the question, consider the
holonomy $A'$ and complex structure $J'$,
induced on the normal bundle $NA_x$ of a leaf, and the associated transversal linearization $B'$ of $B$
along $A_x$, obtained as a limit of $A_x$--transverse rescalings of the original
$M,A,B,J$. This uses a chart adapted to $A_x$ (as for $f$ above) but more to the point,
a holomorphic trivialization $\tau$ of $TM$ along $A_x$, adapted to $A_x$. Observe that
the limit $B'$ of $B$--transforms becomes holomorphic in the limit
(the tangential components are scaled away, analogously to Poincare normal form constructions).
These special cases of the original
problem, with $x\in M'=NA_x,A',B',J'$,
always have transversely holomorphic $B'$, so the Corollary
provides leafwise holomorphic $H_{A'}$, when $J$ is integrable, and conversely,
$J'$ is integrable if $H_{A'}$ is holomorphic.
Thus, by comparing, in the context of $M'$, the
Nijenhuis integrability condition in the ($A,B$ adapted) form above,
with the criterion suggested by the Corollary, it now seems clear that these are
equivalent.
Note that the transverse linearization, which gives $M'$, stabilizes the Nijenhuis system (equation (1)) along a leaf
$A_x$, just as it stabilizes $H_{A'}$.
(Furthermore, they have very similar formal structure and both provide the integrability conditions.
It may be more direct to just do the calculation, but these geometric constructions may have
some further usefulness as we will see below.)
This leads us to the desired criterion:
{\bf Main Claim}:
$J$ is integrable on $U$, an open set,
iff
the A-maps $NH:A_x\to {{\cal J}_N}$ are A-leafwise holomorphic, for all $x\in U$,
and likewise with
$A,B$ interchanged.
(ie holomorphicity of the A-maps and B-maps together is necessary and sufficient).
Our discussion of this criterion so far relies implicitly on the Newlander--Nirenberg theorem.
We
propose to consider a direct geometric construction which might eliminate this dependence: given as data
leafwise holomorphic maps, $NH_A, NH_B$, the goal is to
construct transverse foliations ${\hat A},{\hat B}$ by holomorphic curves on a complex chart, ${\hat M}\subset C^N$
realizing this data. Then to observe that it is diffeo to the given double foliation
with $J$.
In the speculative finishing discussion below, we sketch a possible
new proof of the Newlander--Nirenberg theorem, but only for 4-manifolds,
and
a related possible application to moduli of these
$ M,A,B,J$--structures.
To get started, we use the
preceeding remarks of Robert Bryant giving transverse foliations by pseudo-holomorphic curves
in the almost complex case, which requires 4-dimensionality. Then use the formal equivalence of the
Nijenhuis integrability condition to holomorphiciy of $NH_A, NH_B$, to proceed and use the latter.
The idea for constructing ${\hat M}$ is quite simply to reverse the arguments that led
to holomorphic maps, $NH_A, NH_B$; this would realize transverse foliations ${\hat A},{\hat B}$
by \lq developing' graphs, reversing the proof of the 1st claim (2nd part) above.
There is some ambiguity going backwards from $NH_A, NH_B$ to ${\hat A},{\hat B}$;
one needs to choose a lift from almost complex structures to vector fields, recalling how
${\cal J}$ is a quotient
space of the space (or pseudogroup) of Diffeos of $B_x$, for example. This corresponds well
to the ambiguity, in the presence of ${\hat A},{\hat B}$, of choosing
${\hat M}\subset C^N$ up to biholomorphisms. Also to integrate the transverse vector fields (the lifts)
we use trivializations $\tau$ as above to choose the lift from
$NA$ to $TM$. One has to be careful that these can be chosen without any constraints beyond what
has been discussed here.
Note that $\tau$ exists by a very simple case of Newlander--Nirenberg; the special case of
a transverse linearization, $x\in M'=NA_x,A',B',J'$, as above, ie we must use the integrability, coming from holomorphicity
of $H'= NH$.
Note that the integrability criterion of the corollary above is nontrivial, since $NH$, along a single leaf, can be arbitrarily
specified, in the almost
complex, leafwise-integrable case. The construction sketched here now seems to suggest
that the whole family of $NH_A, NH_B$
can also be specified quite freely. This would mean that they give good moduli for
these
$ M,A,B,J$--structures.
To extend this reconstruction of an $ M,A,B,J$--structure to higher dimensions,
from data such as holomorphic $NH_A$, one might use large families of (pseudo-)holomorphic
curves; we are guessing that sprays of such curves that cover the tangent bundle of $M$ could have enough Jacobi-fields
(ie holonomy) to formally express the Nijenhuis condition.
