(1) We first show that $\star$ is associative. This can be done through the following lemma.

Lemma 1. $f_{X\star Y} = f_X \circ f_Y$.

Proof. Note that
$$\begin{align*} f_{X \star Y}(\mathbb{N}) &= \mathbb{N} - (X \star Y) = (\mathbb{N} - X) - f_X(Y) \\ &= f_X(\mathbb{N}) - f_X(Y) = f_X(\mathbb{N} - Y) = f_X(f_Y(\mathbb{N})) \end{align*}$$
This means that the functions $f_{X \star Y}$ and $f_X \circ f_Y$ are strictly increasing functions with the same range. This forces that the two must be the same. $\square$.

The lemma implies associativity since
$$\begin{align*} \mathbb{N} - ((A \star B) \star C) &= f_{(A \star B) \star C}(\mathbb{N}) = f_A(f_B(f_C(\mathbb{N}))) \\ &= f_{A \star (B \star C)}(\mathbb{N}) = \mathbb{N} - (A \star (B \star C)), \end{align*}$$
so $(A \star B) \star C = A \star (B \star C)$.

(2) Due to the associativity, let us define $X^{*k} = X \star X \star \dots \star X$, where $X$ appears $k$ times on the RHS. Our goal is to show that $A^{*b} = B^{*a}$. This can be obtained through the following lemma:

Lemma 2. If $X \star Y = Y \star X$ and $|X| = |Y|$, then $X = Y$.

If Lemma 2 holds, then due to the fact that
(i) $|A^{*b}| = ab = |B^{*a}|$;
(ii) Since $A \star B = B \star A$, by Lemma 1, we have $A^{*b} \star B^{*a} = B^{*a} \star A^{*b}$.
So by Lemma 2, we have $A^{*b} = B^{*a}$.

Hence, it remains to prove Lemma 2. Assume $X \neq Y$. Let $s$ be the largest number in exactly one of $X$ and $Y$; WLOG we assume $s \in X - Y$. The number $f_X(s)$ counts the $s$-th number not in $X$, which implies that
$$f_X(s) = s + |X \cap \{1, 2, \dots, f_X(s)\}|. \quad (1)$$
Since $f_X(s) \geq s$, we have that
$$\{f_X(s) + 1, f_X(s) + 2, \dots, \} \cap X = \{f_X(s) + 1, f_X(s) + 2, \dots\} \cap Y,$$
which, together with the assumption that $|X| = |Y|$, gives
$$|X \cap \{1, 2, \dots, f_X(s)\}| = |Y \cap \{1, 2, \dots, f_X(s)\}|. \quad (2)$$
Now, consider the equation
$$t - |Y \cap \{1, 2, \dots, t\}| = s.$$
This equation is satisfied only when $t \in [f_Y(s), f_Y(s+1))$, because the left hand side counts the number of elements up to $t$ that are not in $Y$. We have that the value $t = f_X(s)$ satisfies the above equation because of (1) and (2). Furthermore, since $f_X(s) \notin X$ and $f_X(s) \ge s$,
we have that $f_X(s) \notin Y$ due to the maximality of $s$. Thus, by the above discussion, we must have $f_X(s) = f_Y(s)$.

Finally, we arrive at a contradiction. The value $f_X(s)$ is neither in $X$ nor in $f_X(Y)$, because $s$ is not in $Y$ by assumption. Thus, $f_X(s) \notin X \star Y$. However, since $s \in X$, we have $f_Y(s) \in Y \star X$, a contradiction.