Choi's theorem states that any completely positive map $\Phi(\cdot) : C^*_{n\times n} \rightarrow C^*_{m \times m}$ can be expressed as $\Phi(\rho) = \sum_{j=1}^r F_j^\dagger \rho F_j$, for some $n \times m$ matrices $F_j$. In order for the map to be trace preserving one needs to have $\sum_j F_j F_j^\dagger = I_n$.
How is this trace preserving condition derived? I couldn't see it.
This is a slight variation of the ideas behind the other answer.
Note that $\operatorname{Tr}(\Phi(\rho))=\operatorname{Tr}(\rho)$ for all states $\rho$ (read, all positive trace-1 operators) is equivalent to $\operatorname{Tr}(\Phi(X))=\operatorname{Tr}(X)$ holding for all operators $X$ (essentially because any operator can be written as a linear combination of positive operators, and the trace operation is linear).
Note that if $\Phi(X)=\sum_k A_k X A_k^\dagger$, then $\operatorname{Tr}(\Phi(X))=\operatorname{Tr}(X)$ is equivalent to $$\operatorname{Tr}\left[X\left(\sum_k A_k^\dagger A_k\right) \right]=\operatorname{Tr}(X).$$
Because this must hold for any operator $X$, we can see what it amounts to for $X=\lvert i\rangle\!\langle j\rvert$. Noting that $\operatorname{Tr}[|i\rangle\!\langle j| B]=\langle j|B| i\rangle$ and $\operatorname{Tr}[|i\rangle\!\langle j|]=\delta_{ij}$, this gives us $$\langle i|\sum_k A_k^\dagger A_k |j\rangle=\delta_{ij}.$$
This is nothing but the componentwise version of $\sum_k A_k^\dagger A_k=I$.
Note that here I used a slightly different notational convention for the Kraus decomposition than the one used in the original post. The reason is simply that I am more used to this one, but you might simply replace each $A_k\to A_k^\dagger$ switch between the two conventions.
Recall that the trace is both linear and invariant under cyclic permutation of the operators
$$ \mathrm{Tr}(\Phi(\rho))=\mathrm{Tr}\left(\sum_j F_j^\dagger \rho F_j\right)=\sum_j\mathrm{Tr}\left( F_j^\dagger \rho F_j\right)=\sum_j \mathrm{Tr}\left(F_jF_j^\dagger \rho \right)= \mathrm{Tr}\left(\sum_jF_jF_j^\dagger \rho \right)$$
You can clearly see that if $\sum_jF_jF_j^\dagger=I$ $\mathrm{Tr}(\Phi(\rho))=\mathrm{Tr}(\rho)$ for all $\rho$. To prove the converse, suppose $A$ is such that
$$\mathrm{Tr}(A\rho)=\mathrm{Tr}(\rho) $$ for all $\rho$, this corresponds to
$$ \sum_{ij}A_{ij}\rho_{ji}-\sum_i \rho_{ii}=0$$
By taking $\rho_{ij}=\delta_{ki}\delta_{lj}$
we get
$$A_{lk}-\delta_{lk}=0 $$
thus $A=I$.
