Publish-subscribe is an increasingly popular messaging pattern for distributed systems, supporting scalable and extensible programming, and optimal spatial, temporal, and control-flow decoupling of distributed components. Publish-subscribe middleware and methods were extended towards supporting security, in particular confidentiality, and increased availability, yet a few prior works addressed anonymity of participants. Anonymity of senders and receivers may however be crucial, e.g., for supporting freedom of expression in regimes where political repression and censorship prevail. In this article, we review basic security and privacy requirements and introduce a new attacker model based on statistical disclosure, used to challenge anonymity. We elaborate on design options for privacy-preserving publish-subscribe systems and present a novel system that leverages peer-to-peer networking concepts; this novel approach protects subscriber anonymity by means of Probabilistic Forwarding (PF) and through a novel so-called Shell Game (SG) algorithm. We verify our solution against the requirements and provide a simulation-based analysis of the effectiveness of our approaches in light of our attacker model. The results show that the SG algorithm efficiently protects subscriber anonymity, and that anonymity sets can be adjusted via PF.