The prime ideals of $(\mathbb{N},\cdot,1,0)$
Let $\mathbb{P}$ be the set of prime numbers. There is a bijection$^1$
$$\mathcal{P}(\mathbb{P}) \to \mathrm{Spec}_{\mathbf{CMon}_0}((\mathbb{N},\cdot,1,0)),~ E \mapsto \langle E \rangle,$$
which maps a set of prime numbers to the ideal generated by it. Explicitly, we have $\langle \emptyset \rangle = \{0\}$ and $\langle E \rangle = \bigcup_{p \in E} p\mathbb{N}$ for $E \neq \emptyset$.
Proof. With the explicit description of $\langle E \rangle$ it is easy to see that $\langle E \rangle$ is indeed a prime ideal with $E = \langle E \rangle \cap \mathbb{P}$. Let $I$ be a prime ideal and $E := I \cap \mathbb{P}$. Clearly, $\langle E \rangle \subseteq I$. Conversely, if $n \in I$, w.l.o.g. $n \neq 0$, we may factor $n$ as a product of prime numbers. Since $I$ is prime, one of the prime numbers, say $p$, must be contained in $I$. Then $p \in E$ and $n \in p\mathbb{N}$, so $n \in \langle E \rangle$. $\square$
The homomorphism $(\mathbb{N},\cdot,1,0) \hookrightarrow (\mathbb{Z},\cdot,1,0)$ induces a bijection on the spectra (you only need to check that a prime ideal $I \subseteq \mathbb{Z}$ satisfies $I = (I \cap \mathbb{N}) \cup -(I \cap \mathbb{N}$), which is easy). So we also have a bijection $\mathcal{P}(\mathbb{P}) \to \mathrm{Spec}_{\mathbf{CMon}_0}((\mathbb{Z},\cdot,1,0))$, $E \mapsto \langle E \rangle$.
Direct sums
Here is a more conceptual explanation and generalization.
Let $(M_i)_{i \in \mathbb{N}}$ be a family of commutative monoids (not with zero at this point), written multiplicatively. Their coproduct $\coprod_{i \in I} M_i$ is the "direct sum" $\bigoplus_{i \in I} M_i \subseteq \prod_{i \in I} M_i$ consisting of those tuples which are $1$ almost everywhere. The inclusions $\iota_i : M_i \hookrightarrow \bigoplus_{i \in I} M_i$ induce maps $\mathrm{Spec}_{\mathbf{CMon}}(\bigoplus_{i \in I} M_i) \to \mathrm{Spec}_{\mathbf{CMon}}(M_i)$ and hence a map
$$\alpha : \mathrm{Spec}_{\mathbf{CMon}}(\bigoplus_{i \in I} M_i) \to \prod_{i \in I} \mathrm{Spec}_{\mathbf{CMon}}(M_i).$$
Conversely, given a family of prime ideals $\mathfrak{p}_i \subseteq M_i$, the ideal $\langle \bigcup_{i \in I} \mathfrak{p}_i \rangle = \bigcup_{i \in I} \langle \mathfrak{p}_i \rangle \subseteq \bigoplus_{i \in I} M_i$ is a prime ideal which restricts to the $\mathfrak{p}_i$ along $\iota_i$. If $\mathfrak{p} \subseteq \bigoplus_{i \in I} M_i$ is any prime ideal, consider some element $m = \prod_{i \in I} m_i \in \mathfrak{p}$. Since $\mathfrak{p}$ is prime, we have $m_i \in \mathfrak{p}$ for some $i$, so $m_i \in \mathfrak{p} \cap M_i$, and since $m$ is a multiple of $m_i$, we see $m \in \langle \mathfrak{p} \cap M_i \rangle$. This shows that $\alpha$ is bijective. (Actually, $\alpha$ is an isomorphism of ringed spaces.)
Adjoining a zero
Notice that for every $M \in \mathbf{CMon}$ there is a canonical bijection
$$\mathrm{Spec}_{\mathbf{CMon}_0}(M \cup \{0\}) \to \mathrm{Spec}_{\mathbf{CMon}}(M),~ \mathfrak{p} \mapsto \mathfrak{p} \cap M.$$
The prime ideals of $(\mathbb{N},\cdot,1,0)$ again
The monoid $(\mathbb{N},+,0)$ has exactly two prime ideals, namely $\emptyset$ and $\mathbb{N}^+$. Prime factorization yields an isomorphism
$(\mathbb{N},\cdot,1,0) \cong (\mathbb{N}^+,\cdot,1) \cup \{0\} \cong \bigl(\bigoplus_{p \in \mathbb{P}} (\mathbb{N},+,0) \bigr) \cup \{0\}$. Thus, the previous results show that
$$\mathrm{Spec}_{\mathbf{CMon}_0}((\mathbb{N},\cdot,1,0)) \cong \prod_{p \in \mathbb{P}} \mathrm{Spec}_{\mathbf{CMon}}((\mathbb{N},+,0)) = \prod_{p \in \mathbb{P}} \{\emptyset,\mathbb{N}^+\} \cong \mathcal{P}(\mathbb{P}).$$
Finally, the tensor product
Now we can also compute the prime ideals of $(\mathbb{N},\cdot,1,0) \otimes_{\mathbb{F}_1} (\mathbb{N},\cdot,1,0)$. It is $(\mathbb{N}^+,\cdot,1) \otimes_{\mathbb{F}_0} (\mathbb{N}^+,\cdot,1)$ with an adjoined zero. The tensor product refers to commutative $\mathbb{F}_0$-algebras aka commutative monoids; I will just write $\otimes$ since the object themselves show which category we are in. We have
$$(\mathbb{N}^+,\cdot,1) \otimes (\mathbb{N}^+,\cdot,1) \cong \bigoplus_{p,q \in \mathbb{P}} (\mathbb{N},+,0) \otimes (\mathbb{N},+,0) \cong \bigoplus_{p,q \in \mathbb{P}} (\mathbb{N},+,0)$$
and therefore
$$\mathrm{Spec}_{\mathbf{CMon}}((\mathbb{N},\cdot,1,0) \otimes_{\mathbb{F}_1} (\mathbb{N},\cdot,1,0)) \cong \mathrm{Spec}_{\mathbf{CMon}}((\mathbb{N}^+,\cdot,1) \otimes (\mathbb{N}^+,\cdot,1)) \cong \mathcal{P}(\mathbb{P} \times \mathbb{P}).$$
Explicitly, the prime ideal associated to a subset $E \subseteq \mathbb{P} \times \mathbb{P}$ is $\bigcup_{(p,q) \in E} \langle p \otimes 1, 1 \otimes q \rangle$ (I think).
$^1$It is a really good idea to not forget forgetful functors in general, especially here when we need to emphasize the multiplicative structure and the zero. This is why I don't just write $\mathbb{N}$, which is merely the underlying set of the monoid with zero $(\mathbb{N},\cdot,1,0)$.
$^2$The term "binoid" is a bad choice here, I won't use it.
Combining your two approaches, let's take \begin{align*}\Phi: \mathbb Z/(m_1)\otimes_{\mathbb Z/(n)}\mathbb Z/(m_2)&\to\mathbb Z/(m_1,m_2)\\(z_1+(m_1))\otimes_{\mathbb Z/(n)}(z_2+(m_2))&\mapsto z_1z_2+(m_1,m_2) \end{align*} and \begin{align*}\Psi:\mathbb Z/(m_1,m_2)&\to \mathbb Z/(m_1)\otimes_{\mathbb Z/(n)}\mathbb Z/(m_2)\\z+(m_1,m_2)&\mapsto(z+(m_1))\otimes_{\mathbb Z/(n)}(1+(m_2))\end{align*}
(I am using capital letters for the functions to avoid possible confusion with the functions in the question. Also note that I will write $\overline z$ for the residue class of $z$ when the context is clear, and also drop the indeces from tensor products.)
It is straightforward to show that $\Phi$ is a well-defined homomorphism using the universal property of tensor products. To show that $\Psi$ is well-defined, take $z,z'\in\mathbb Z$ such that $z-z'\in(m_1,m_2)$ and show that $\Psi(\overline z)=\Psi(\overline{z'}).$ It should be clear that $\Psi$ is a homomorphism.
Now, all that is left to do is to show that these two functions are inverses of each other. One direction $\Phi\circ\Psi=\mathrm{id}$ is obvious, the other one needs a little more work. Take a general element of $\mathbb Z/(m_1)\otimes\mathbb Z/(m_2)$, it has the form $z=\sum_{i=1}^n\overline x_i\otimes\overline y_i$. Then calculate \begin{align*}\Psi(\Phi(z))&=\sum_{i=1}^n\Psi(\overline{x_iy_i})\\&=\sum_{i=1}^n(x_iy_i+(m_1))\otimes(1+(m_2))\\&=\sum_{i=1}^n(y_i+(n))\cdot((x_i+(m_1))\otimes(1+(m_2)))\\&=\sum_{i=1}^n(x_i+(m_1))\otimes(y_i\cdot1+(m_2))=z,\end{align*} as desired.
Best Answer
The computation of the tensor product of commutative monoids $\mathbb{Z} \otimes \mathbb{Z}$ can be reduced to the computation of $(\mathbb{Z} \setminus \{0\}) \otimes (\mathbb{Z} \setminus \{0\})$ as follows.
More generally, let $M$ be any commutative monoid (for example, $\mathbb{Z} \setminus \{0\}$ under multiplication). Then $M \sqcup \{0\}$ is a commutative monoid with zero which contains $M$ as a submonoid. This construction is left adjoint to the forgetful functor from commutative monoids with zero to commutative monoids. But since we only work with commutative monoids, here the universal property is a bit more complicated: $$\hom(M \sqcup \{0\},N) \cong \{(u,f) \in M \times \hom(M,N) : u \text{ absorbs } f(M)\}.$$ The condition means that $u \cdot f(m) = u$ for all $m \in M$. Since the tensor product can also be defined by the hom-tensor-adjunction, this easily implies that (and a direct proof is also possible) $$(M \sqcup \{0\}) \otimes N \cong (N \oplus (M \otimes N)) / (n \cdot (m \otimes n) = n)_{m \in M, n \in N}.$$ The quotient means that we mod out the smallest congruence relation which makes $n \cdot (m \otimes n)$ and $n$ equivalent, for all $m \in M$, $n \in N$. We can use this twice to deduce $$(M \sqcup \{0\}) \otimes (N \sqcup \{0\}) \cong (M \oplus N \oplus (M \otimes N)) \sqcup \{0\}/\\ (n \cdot (m \otimes n) = n,\, m \cdot (m \otimes n) = m)_{m \in M, n \in N}.$$ As already said in my comment, notice that the tensor product is much easier if we work in the category of commutative monoids with zero, since in that case we just have $(M \sqcup \{0\}) \otimes_0 (N \sqcup \{0\}) \cong (M \otimes N) \sqcup \{0\}$ by general nonsense.