This paper investigates automatic repeat request (ARQ) retransmission protocols for two-way wireless relay networks based on network coding (NC). The idea of NC is applied to increase the achievable throughput for the exchange of information between two terminals through one relay. Using NC, throughput efficiency is significantly improved due to the reduction of the number of retransmissions. Particularly, two improved NC-based ARQ schemes are designed based on go-back-N and selective-repeat protocols. The analysis of throughput efficiency is then carried out to find the best retransmission strategy for different scenarios. Finally, simulation results are provided to verify the theoretical analysis.