In this paper, we analyze the outage probability of an amplify-and-forward (AF) cooperative non-orthogonal multiple access (NOMA) model in multi-relay multiuser networks. In contrast to conventional cooperative networks, relays in the considered network have no embedded energy supply; they need to rely on the energy harvested from the signals broadcasted by the source for their cooperative NOMA transmission. Based on this structure, a new relay selection scheme is proposed, considering both channel state information (CSI) and battery status of relays. Assuming each relay has infinite or finite energy storage for accumulating energy, we use the infinite or finite Markov chain to capture the evolution of relay batteries and certain simplified assumptions to reduce computational complexity of the Markov chain analysis. The approximate closed-form expressions for the outage probability of the proposed scheme are derived therefrom. All theoretical results are validated by numerical simulations. The impacts of the system parameters, such as relay number, energy harvesting threshold and battery size, on the performance are extensively investigated.