The operation of communication protocols is conventionally independent of the information being transmitted. This paper puts forth the notion of protocol coding to refer to transmission strategies in which data can be encoded by modulating the protocol actions according to the information message. We focus on communication in the presence of half-duplex constraints, where the task of the protocol is to schedule the transmission/reception times of different nodes. Such a schedule is conventionally decided a priori in the form of time-sharing. While previous work has focused on protocol coding for standard relay channels, this paper tackles two-way communications aided by a relay. Since the techniques developed for standard relay channels cannot be applied to the scenario at hand, a novel simple strategy is proposed that is tailored to two-way communications. The proposed scheme is shown to significantly outperform conventional time-sharing for a deterministic two-way relay channel.