We apply non-binary coding to the two-way relay channel and evaluate two decoding schemes for the multiple-access phase at the relay: joint decoding for both users and separate decoding for a linear combination of both packets. We evaluate several efficient modulation schemes which combine favorably with non-binary coding and find that joint decoding can offer significant performance benefits.