We study the electric dipole moment (EDM) and the anomalous magnetic dipole moment (MDM) of the muon in the CP-violating Minimal Supersymmetric extension of the Standard Model (MSSM). We take into account the contributions from the chargino- and neutralino-mediated one-loop graphs and the dominant two-loop Higgs-mediated Barr-Zee diagrams. We improve earlier calculations by incorporating CP-violating Higgs-boson mixing effects and the resummed threshold corrections to the Yukawa couplings of the charged leptons as well as that of the bottom quark. The analytic correlation between the muon EDM and MDM is explicitly presented at one- and two-loop levels and, through several numerical examples, we illustrate its dependence on the source of the dominant contributions. We have implemented the analytic expressions for the muon EDM and MDM in an updated version of the public code CPsuperH2.0.