Polarization-division multiplexed (PDM) transmission based on the nonlinear Fourier transform (NFT) is proposed for optical fiber communication. The NFT algorithms are generalized from the scalar nonlinear Schrödinger equation for one polarization to the Manakov system for two polarizations. The transmission performance of the PDM nonlinear frequency-division multiplexing (NFDM) and PDM orthogonal frequency-division multiplexing (OFDM) are determined. It is shown that the transmission performance in terms of Q-factor is approximately the same in PDM-NFDM and single polarization NFDM at twice the data rate and that the polarization-mode dispersion does not seriously degrade system performance. Compared with PDM-OFDM, PDM-NFDM achieves a Q-factor gain of 6.4 dB. The theory can be generalized to multi-mode fibers in the strong coupling regime, paving the way for the application of the NFT to address the nonlinear effects in space-division multiplexing.