We study the structure of quantum states for a binary mixture of spin-1 atomic Bose-Einstein condensates. In contrast to collision between identical bosons, the s-wave scattering channel between interspecies does not conform to a fixed symmetry. The spin-dependent Hamiltonian thus contains noncommuting terms, making the exact eigenstates more challenging to obtain because they now depend more generally on both the intra- and interspecies interactions. We discuss two limiting cases, where the spin-dependent Hamiltonian reduces respectively to sums of commuting operators. All eigenstates can then be directly constructed, and they are independent of the detailed interaction parameters.