In this paper, non-orthogonal multiple access (NOMA) is applied to large-scale underlay cognitive radio (CR) networks with randomly deployed users. In order to characterize the performance of the considered network, new closed-form expressions of the outage probability are derived using stochastic-geometry. More importantly, by carrying out the diversity analysis, new insights are obtained under the two scenarios with different power constraints: 1) fixed transmit power of the primary transmitters (PTs), and 2) transmit power of the PTs being proportional to that of the secondary base station. For the first scenario, a diversity order of $m$ is experienced at the $m$-th ordered NOMA user. For the second scenario, there is an asymptotic error floor for the outage probability. Simulation results are provided to verify the accuracy of the derived results. A pivotal conclusion is reached that by carefully designing target data rates and power allocation coefficients of users, NOMA can outperform conventional orthogonal multiple access in underlay CR networks.