We examine the conformations and effective interactions of star-branched polyelectrolytes with and without added salt, by employing monomer-resolved molecular dynamics simulations and an analytical theory. The simulations take into account the excluded-volume and Coulomb interactions between the individual monomers, as well as the counter- and coions. The theory is based on a variational free energy that is written as a sum of electrostatic, polymer, and entropic contributions of the counter- and coions. For the conformations of isolated polyelectrolyte stars, we find strong stretching of the chains, resulting in a linear scaling of the star radius with the degree of polymerization, as well as trapping and condensation of a large fraction of counterions. The effective interactions at arbitrarily strong overlaps between the stars are shown to be dominated by the entropic contributions of the trapped counterions, with the electrostatic contribution playing only a minor role due to an almost complete neutralization of the stars. In the case of added salt, we find a shrinking of the star size as well as a weakening of the effective force due to a generalized depletion mechanism. The good agreement between theory and simulations allows us to put forward analytic expressions for the effective interaction between polyelectrolyte stars at arbitrary separations.