Suppose I am working in $\mathbb{R}^n$, where $\boldsymbol{x} \in \mathbb{R}^n$ is an arbitrary point, and I have a vector field $\boldsymbol{n} : \mathbb{R}^n \mapsto \mathbb{R}^n$. I would like to interpret $\boldsymbol{n}(\boldsymbol{x})$ as the normals to a set of 'surfaces' ($n-1$ dimensional manifolds) which divide up the space, however I do not expect this to always be the case and there must be some condition(s) that $\boldsymbol{n}(\boldsymbol{x})$ must satisfy to foliate the space in this way.
In my attempting to find out what this condition could be, I found the Frobenius Theorem, however my differential geometry is not good enough to understand if this is exactly what I want. If this is the result I am after, could someone please explain how to turn this theorem into a condition on $\boldsymbol{n}$? Or else explain how to construct such a condition?
Frobenius is indeed the way to go. Frobenius' theorem, roughly speaking, answers the question of whether we can 'integrate' various subspaces to actually form an immersed submanifold.
Given your unit vector field $\boldsymbol{n}$, we shall consider at each point $x\in\Bbb{R}^n$, the subspace $E_x=(\text{span}\{\boldsymbol{n}(x)\})^{\perp}$, the orthogonal complement of the vector $\boldsymbol{n}(x)$. The subspace $E_x$ has dimension $n-1$, and we should really think of it as being a subspace of the tangent space $T_x\Bbb{R}^n\cong \{x\}\times\Bbb{R}^n$. An equivalent way of describing this situation is to convert the vector field into a 1-form using the standard inner product on $\Bbb{R}^n$, i.e if $\boldsymbol{n}$ has component functions $(f_1,\dots, f_n)$ with respect to the standard basis, then consider the 1-form \begin{align} \omega=f_1\,dx^1+\dots+f_n\,dx^n, \end{align} where $(x^1,\dots, x^n)$ are standard Cartesian coordinates. Then, the subspace $E_x$ is precisely the kernel of $\omega_x:T_x\Bbb{R}^n\to\Bbb{R}$. In other words, a vector $v_x\in T_x\Bbb{R}^n$ is orthogonal to $\boldsymbol{n}(x)$ if and only if $\omega_x(v)=0$.
Now, writing things in terms of differential forms is nice because computations are usually easy with them. The Frobenius condition is that \begin{align} (d\omega)\wedge \omega&=0.\tag{$*$} \end{align} Let us now write out the condition $(*)$ more explicitly. First, \begin{align} d\omega &=\sum_{j=1}^ndf_j\wedge dx^j=\sum_{i,j=1}^n\frac{\partial f_j}{\partial x^i}\,dx^i\wedge dx^j. \end{align} So, \begin{align} (d\omega)\wedge\omega&=\sum_{i,j,k=1}^n\frac{\partial f_j}{\partial x^i}\cdot f_k\,dx^i\wedge dx^j\wedge dx^k\\ &=\sum_{1\leq i<j<k\leq n}\left[ f_i\left(\frac{\partial f_k}{\partial x^j}-\frac{\partial f_j}{\partial x^k}\right)+ f_j\left(\frac{\partial f_i}{\partial x^k}-\frac{\partial f_k}{\partial x^i}\right)+ f_k\left(\frac{\partial f_j}{\partial x^i}-\frac{\partial f_i}{\partial x^j}\right) \right]\,dx^i\wedge dx^j\wedge dx^k, \end{align} where the last equality used the alternating nature of the wedge product $dx^i\wedge dx^j\wedge dx^k$. Since the collection $\{dx^i\wedge dx^j\wedge dx^k\,:\, 1\leq i<j<k\leq n\}$ is a basis of $3$-forms on $\Bbb{R}^n$, this vanishes if and only if the stuff in square brackets vanishes for all $1\leq i<j<k\leq n$: \begin{align} f_i\left(\frac{\partial f_k}{\partial x^j}-\frac{\partial f_j}{\partial x^k}\right)+ f_j\left(\frac{\partial f_i}{\partial x^k}-\frac{\partial f_k}{\partial x^i}\right)+ f_k\left(\frac{\partial f_j}{\partial x^i}-\frac{\partial f_i}{\partial x^j}\right)&=0.\tag{$**$} \end{align} So, $(**)$ is the condition you seek.
An equivalent (but not a very good IMO) way of thinking about this condition is that if you consider $F_{ijk}=(f_i,f_j,f_k)$, the 'curl' with respect to the $i,j,k$ variables must be orthogonal to $F_{ijk}$: $(\nabla_{ijk}\times F_{ijk})\cdot F_{ijk}=0$. So, in the special case of $n=3$ dimensions, the condition is that $(\nabla\times \boldsymbol{n})\cdot \boldsymbol{n}=0$. In $n=1$ or $n=2$ dimensions, this condition is trivially satisfied.
Also, I should remark that for concrete calculations, the condition $(**)$ is very tedious to verify because there are too many indices lying around. It is much better to just compute the 3-form $(d\omega)\wedge \omega$ using the rules of exterior differentiation, and check whether or not it vanishes.