Decoherence of a center spin or qubit in a spin bath is essentially determined by the many-body bath evolution. The bath dynamics can start either from a pure state or, more generally, from a statistical ensemble. In the preceding article [W. Yang and R. B. Liu, Phys. Rev. B \textbf{78}, 085315 (2008)], we have developed the cluster-correlation expansion (CCE) theory for the so-called single-sample bath dynamics initiated from a factorizable pure state. Here we present the ensemble CCE theory, which is based on similar ideas of the single-sample CCE: The bath evolution is factorized into the product of all possible cluster correlations, each of which accounts for the authentic (non-factorizable) collective excitation of a group of bath spins, and for the finite-time evolution in the qubit decoherence problem, convergent results can be obtained by truncating the ensemble CCE by keeping cluster correlations up to a certain size. A difference between the ensemble CCE and single-sample CCE is that the mean-field treatment in the latter formalism of the diagonal part of the spin-spin interaction in the bath is not possible in the former case. The ensemble CCE can be applied to non-factorizable initial states. The ensemble CCE is checked against the exact solution of an XY spin bath model. For small spin baths, it is shown that single-sample dynamics is sensitive to the sampling of the initial state from a thermal ensemble and hence very different from the ensemble average. ; Comment: 7 pages, 3 figures