Definitions
Let $\mathcal{H}$ be a complex Hilbert space. It turns out that the set $L(\mathcal{H})$ of all linear operators on $\mathcal{H}$ is also a Hilbert space. Let $I_\mathcal{H}$ denote the identity map on $\mathcal{H}$.
Definition 1. A linear map $\Phi:L(\mathcal{H})\to L(\mathcal{H})$ is said to be trace-preserving if
$$
\mathrm{tr}(\Phi(A))=\mathrm{tr}(A)\tag1
$$
for every linear operator $A\in L(\mathcal{H})$.
Definition 2. A linear map $\Phi:L(\mathcal{H})\to L(\mathcal{H})$ is said to be positive if it sends every positive semidefinite operator to a positive semidefinite operator.
Definition 3. A linear map $\Phi:L(\mathcal{H})\to L(\mathcal{H})$ is said to be completely positive if the linear map $\Phi\otimes I_\mathcal{H'}$ is positive for every Hilbert space $\mathcal{H'}$.
Finally,
Definition 4. A linear map $\Phi:L(\mathcal{H})\to L(\mathcal{H})$ is said to be CPTP if it is completely positive and trace-preserving.
Intuition
The concept of the CPTP map arises in the analysis of the constraints that a mathematical function on $L(\mathcal{H})$ must satisfy in order for it to correspond to a transformation realizable as physical dynamics of an open quantum system$^1$. First and foremost, any such function must be linear. However, this is not sufficient.
The key fact motivating the above definitions is that in density matrix formalism of quantum mechanics the spectrum of a linear operator encodes a classical probability distribution. Therefore, if a linear function on $L(\mathcal{H})$ is to represent a physical dynamical transformation, then it must send an operator whose spectrum is a valid probability distribution to another operator with such a spectrum.
More precisely, if the input eigenvalues sum up to one, then the output eigenvalues must sum up to one. This is what definition 1 says. Further, if the input eigenvalues are non-negative, then the output eigenvalues must be non-negative. This is what definition 2 says. Somewhat unexpectedly, it turns out that if a positive map acts on a subsystem, then a map$^2$ acting on a larger system may fail to be positive. This is why we need definition 3. Finally, definition 4 collects all these constraints into one concept: the CPTP map.
Matrix representation
In general, the matrix of $\Phi:L(\mathcal{H})\to L(\mathcal{H})$ in an arbitrary operator basis does not immediately divulge its complete positivity. However, we can think of $\Phi$ as an order $4$ tensor with four indices: input row, input column, output row, output column rather than an order $2$ tensor (aka a matrix). Looking at $\Phi$ from this perspective, we see that there is more than one way to represent it as a matrix. Indeed, we can combine the four indices into a pair of composite indices in a few different ways.
If input row and output row indices are combined to give the matrix row index and input column and output column indices are combined to give the matrix column index, then the resulting matrix $C(\Phi)$ is called the Choi matrix.
This matrix is different than the matrix $K(\Phi)$ obtained by following the standard linear algebra procedure for a given choice of operator basis in $L(\mathcal{H})$. However, $C(\Phi)$ makes it easier to determine complete positivity of $\Phi$ than $K(\Phi)$, because of the following
Theorem. $\Phi$ is completely positive if and only if $C(\Phi)$ is positive semidefinite.
$^1$ The formalism of quantum channels makes an important hidden assumption that the input to the channel and its environment are independent. Crucially, if the environment contains systems that participated in input preparation then the dynamics may fail to be described by a linear map. See closing remarks in Chapter 8 of Nielsen & Chuang.
$^2$ Transpose $T(A)=A^T$ is positive since it preserves the eigenvalues. However, $T\otimes I$ sends rank one projector onto $\mathrm{span}(|00\rangle,|11\rangle)$ to a matrix with eigenvalue $-1$.
