Let $M$ and $N$ be mappings from $\mathcal{S}(H_A \otimes H_B)$ to itself, where $\mathcal{S}(H)$ denotes the set of density operators over the Hilbert space $H$.
If the following two conditions hold:
(i) both $M$ and $N$ are linear over $\mathcal{S}(H_A \otimes H_B)$
(ii) $M(\rho_A \otimes \rho_B) = N(\rho_A \otimes \rho_B)$ for all $\rho_A \in \mathcal{S}(H_A)$ anf $\rho_B \in \mathcal{S}(H_B)$ - i.e. they have the same behaviour on product states
Does it follow that $N = M$?
I am convinced this should work, but am struggling to find a proof (or, if it does not hold, an explicit example).
Yes. But there are some things to discuss first to help you understand.
When discussing a "linear mapping" one typically requires that it be defined on a full linear space, not some convex subset. For now, let $B(H)$ denote the linear space of all bounded linear operators on $H$, then $S(H)$ is a convex subset of $B(H)$.
Now we can use linearity of $M$ to allow for the equality $M(\alpha X + \beta Y) = \alpha M(X) + \beta M(Y)$ to hold for arbitrary operators $X$ and $Y$ and arbitrary complex numbers $\alpha$ and $\beta$ (i.e., not just for density operators).
Because $M$ and $N$ agree on all product density operators, by linearity of $M$ and $N$ they must agree on all product operators as well. That is, it must be the case that $$M(X\otimes Y) = N(X\otimes Y)$$ holds for all $X\in B(H_A)$ and $Y\in B(H_B)$.
If $H_A$ and $H_B$ are finite-dimensional Hilbert spaces, then $B(H_A)$, $B(H_B)$ and $B(H_A\otimes H_B)$ are all finite dimensional as vector spaces as well, where we note that $$B(H_A\otimes H_B)\simeq B(H_A)\otimes B(H_B).$$ In this case, the tensor product operator space $B(H_A\otimes H_B)$ is spanned by the product operators, $$ B(H_A\otimes H_B) = \operatorname{span}\big(\big\{X\otimes Y\, :\, X\in B(H_A), Y\in B(H_B)\big\}\big), $$ and so $M$ and $N$ must agree on the whole space.
If they are infinite dimensional, then equality of $M$ and $N$ follows from the universal property of tensor product spaces. See this answer.