Weighted maximum satisfiability is a well-studied problem that has important applicability to artificial intelligence (for instance, MPE inference in Bayesian networks). General-purpose stochastic search algorithms have proven to be accurate and efficient for large problem instances; however, these algorithms largely ignore structural properties of the input. For example, many problems are highly clustered, in that they contain a collection of loosely coupled subproblems (e.g. pipelines of NLP tasks). In this paper, we propose a message passing algorithm to solve weighted maximum satisfiability problems that exhibit this clustering property. Our algorithm fuses local solutions to each subproblem into a global solution by iteratively passing summary information between clusters and recomputing local solutions. Because the size of these messages can become unwieldy for large problems, we explore several message compression techniques to transmit the most valuable information as compactly as possible. We empirically compare our algorithm against a state-of-the-art stochastic solver and show that for certain classes of problems our message passing algorithm finds significantly better solutions.