Is there a parameterization of a neighbourhood of $x\in\mathbb{R}^n$ into two mutually orthogonal sets of variables, with one set parameterizing a pre-defined (n-k)-dimensional submanifold containing $x$? Let $M \subset \mathbb{R}^n$ be a differentiable submanifold with co-dimension $k$. Is there a parameterization of $\mathbb{R}^n$ of a neighbourhood of $x\in M$, so that the variables parameterizing $M$ are orthogonal to the variables parameterizing the directions orthogonal to $M$, throughout the neighbourhood? In other words, I would like a parameterization of the form $\phi:U\subset \mathbb{R}^n \to \mathbb{R}^k\times \mathbb{R}^{n-k}$, such that $\phi^{-1}(0,y) \subset M$ and the variables $x\in \mathbb{R}^k$, $y\in\mathbb{R}^{n-k}$ are orthogonal in $U$, i.e. the metric tensor has the form $g_{ij} = g_{ji} = 0$ for $1\leq i \leq k$, $k+1\leq j \leq n$.  
In case it is relevant, the manifold I am working with is defined as the intersection of level sets $\{ y_i(x)=0\}$, $i=1\ldots k$, where each $y_i$ is smooth enough and the gradients $\{\nabla y_i\}$ are linearly independent on the level set of mutual intersection $M$. I can find a parameterization such that the orthogonality condition holds exactly at $M$, using the variables $y_i$ as the orthogonal directions, as each $\nabla y_i$ is orthogonal to $M$. However, I am wondering how to extend this to a neighbourhood of $M$? 
 A: Set $m=n-k$.
If $m=1$ or $k=1$ then the answer is YES and I hope you know it.
In general, you have $m\cdot k$ equations and 
$n=m+k$ unknowns. 
I.e. if $m\ge 2$ and $k>2$ or if $m> 2$ and $k\ge 2$ then the system is overdetermined.
I think it should be possible to show that there are no solutions in this case.
I do not see what happes in the case $m=k=2$; i.e., for 2-dimensional submanifold in $\mathbb R^4$; maybe there is a solution for any $M$. 
In this case, if $\phi$ is a solution for generic $M$
then for fixed $x$ the points $\phi(x,y)$ do not lie in the normal plane to $\phi(x,0)\in M$; i.e. tubular-neighborhood-construction is useless here.
A: I was reminded of this question recently by a related problem, and I remembered a concept that I had not remembered when I originally saw the question, namely É. Cartan's notion of exterior square of second fundamental forms.  Using that concept, I can give something of an answer to the question.  
It's not definitive, but it does show that, for $n{-}k$ and $k$ sufficiently large, there do exist submanifolds $N^{n-k}\subset\mathbb{R}^n$ that do not occur as a leaf of a (local) foliation whose orthogonal plane field is integrable.  (This is another way to phrase the OP's problem.)
Here is a description of an obstruction:  Suppose that $\mathcal{F}$ and $\mathcal{G}$ are foliations of codimensions $k$ and $n{-}k$, respectively, of an open set $U\subset \mathbb{R}^n$, and suppose that they are orthogonal.  Thus, if $F\subset TU$ is the rank $n{-}k$ bundle of vectors tangent to $\mathcal{F}$ and $G\subset TU$ is the rank $k$ bundle of vectors tangent to $\mathcal{G}$, then $TU=F\oplus G$ is an orthogonal direct sum.  
Let $Q^F$ be the section of $G\otimes\mathsf{S}^2(F)$ that gives the second fundamental forms of the leaves of $\mathcal{F}$ and let $Q^G$ be the section of $F\otimes\mathsf{S}^2(G)$ that gives the second fundamental forms of the leaves of $\mathcal{G}$.  (Note that I am using the metrics on the two bundles to idenfity $F$ with $F^\ast$ and $G$ with $G^\ast$.)  Cartan defined an algebraic exterior square, i.e., a quadratic map
$$
\sigma^F: G\otimes\mathsf{S}^2(F)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F),
$$
which is just the squaring map $G\otimes\mathsf{S}^2(F)\to \bigl(G\otimes\mathsf{S}^2(F)\bigr)\otimes\bigl(G\otimes\mathsf{S}^2(F)\bigr)$, followed by contracting a pair of $F$-indices (so that the result goes into $\bigl(G\otimes F\bigr)\otimes \bigl(G\otimes F\bigr)$), and then followed by skew-symmetrizing in both the $G$- and $F$-pairs independently.  (Note that this map is, of course, zero if either $k=1$ or $n{-}k=1$; otherwise it is not zero.)  On the other side, there is, of course, the corresponding mapping
$$
\sigma^G: F\otimes\mathsf{S}^2(G)\longrightarrow \Lambda^2(G)\otimes\Lambda^2(F).
$$
(Technically, $\sigma^G$ should go into $\Lambda^2(F)\otimes\Lambda^2(G)$, I guess, but I'm 
identifying these two tensor products in the obvious way.)
With all of this defined, a short calculation with the structure equations shows that one has the identity
$$
\sigma^F\bigl(Q^F\bigr) + \sigma^G\bigl(Q^G\bigr) = 0\tag{1}
$$
for any pair of orthogonal foliations $\mathcal{F}$ and $\mathcal{G}$ on an open set $U\subset\mathbb{R}^n$.  
Now, it's a matter of linear algebra to check that, when $k$ and $n{-}k$ are sufficiently large, the maps $\sigma^F$ and $-\sigma^G$ do not have the same image.  This should not be surprising, since, for $k$ and $n{-}k$ sufficiently large, the space $\Lambda^2(G)\otimes\Lambda^2(F)$ is much larger than either $G\otimes\mathsf{S}^2(F)$ or $F\otimes\mathsf{S}^2(G)$, so there is plenty of room for them to have different images.  Their images will also, generally, have different dimensions.
For a specific example, consider the case $k=2$ and $n{-}k=4$.  Then the ranks of $G$ and $F$ are $2$ and $4$ respectively.  It's easy to show that, in this case, $\sigma^F$ is surjective while the image of $\sigma^G$ consists only of elements of the form $a\otimes b$, where $a\in \Lambda^2(G)$ is nonzero and $b\in\Lambda^2(F)$ is a simple $2$-form (i.e., its half-rank is either $0$ or $1$). Thus, if you choose a submanifold $N^4\subset\mathbb{R}^6$ such that the exterior square of its second fundamental form is a nondegenerate $2$-form (and the generic $4$-manifold in $\mathbb{R}^6$ will have this property on a dense open set), then $N^4$ cannot be a leaf of a (local) foliation $\mathcal{F}$ that has an orthogonal foliation $\mathcal{G}$ because, as an equation for $Q^G$, the condition $(1)$ will have no solutions on a neighborhood of $N$.
Notice that $(1)$ is only the first obstruction one would encounter in trying to solve this problem with a prescribed $N^{n-k}\subset\mathbb{R}^n$.  
I believe that the case $n{-}k=k=2$, for which $(1)$ is first a nontrivial condition, though not involutive, will become involutive after the first prolongation, though I haven't checked the details.  So this case is probably OK, at least in the analytic case.  (Note that, even though this case is formally determined, as Anton pointed out in his answer, the symbol of the PDE is degenerate, which is why $(1)$ is still nontrivial in this case, so the 'determined' property is not decisive here.)  
However, even in the 'overdetermined' case $n{-}k=3$ and $k=2$, the equation $(1)$ is always solvable in the sense that $\sigma^F$ and $\sigma^G$ are each surjective, and it could still be (again, I haven't checked) that the system goes into involution after the first prolongation with the proper initial conditions being described in dimension $3$ (instead of dimension $4$). Thus, it's still possible, as far as I know, that every (analytic?) $N^3\subset\mathbb{R}^5$ is a leaf of a foliation that has an orthogonal foliation by surfaces.
