User pairing in Non-Orthogonal Multiple-Access (NOMA) uplink based on channel state information is investigated considering some predefined power allocation schemes. The base station divides the set of users into disjunct pairs and assigns the available resources to these pairs. The combinatorial problem of user pairing to achieve the maximum sum rate is analyzed in the large system limit for various scenarios, and some optimum and sub-optimum algorithms with a polynomial-time complexity are proposed. In the first scenario, $2M$ users and the base station have a single-antenna and communicate over $M$ subcarriers. The performance of optimum pairing is derived for $M\rightarrow \infty$ and shown to be superior to random pairing and orthogonal multiple access techniques. In the second setting, a novel NOMA scheme for a multi-antenna base station and single carrier communication is proposed. In this case, the users need not be aware of the pairing strategy. Furthermore, the proposed NOMA scheme is generalized to multi-antenna users. It is shown that random and optimum user pairing perform similarly in the large system limit, but optimum pairing is significantly better in finite dimensions. It is shown that the proposed NOMA scheme outperforms a previously proposed NOMA scheme with signal alignment.