In this paper, we propose a polarization-aided belief propagation (PA-BP) decoding for M-user uplink non-orthogonal multiple access (NOMA). In this scheme, polar code of each user is regarded as a nested code within a longer polar code with BP decoding, which has the length M times than that of the original user codes. It enables the PA-BP decoder to obtain all user messages with the enhanced channel polarization effect, as compared to the conventional successive interference cancellation BP (SIC-BP) decoder at finite block length. To improve the performance of PA-BP decoder, we further propose interference cancellation (IC) aided-BP (ICA-BP) and ICA-BPL list decoders that incorporates IC during PA-BP iterations. We then analyze the channel capacity of the proposed scheme and use extrinsic information transfer (EXIT) chart to show the convergence behavior of these iterative decoders. By utilizing the Monte Carlo method to optimize this long polar code, simulation results show that the proposed PA-BP outperforms the conventional SIC-BP by 0.8 dB over Gaussian channels, and by 0.7 dB over Rayleigh fading channels. In particular, ICA-BP can achieve more performance gain of 0.4 dB over PA-BP over both channels.