Three independent searches for an electric dipole moment (EDM) of the positive and negative muons have been performed, using spin precession data from the muon g-2 storage ring at Brookhaven National Laboratory. Details on the experimental apparatus and the three analyses are presented. Since the individual results on the positive and negative muon, as well as the combined result, d=-0.1(0.9)E-19 e-cm, are all consistent with zero, we set a new muon EDM limit, |d| < 1.9E-19 e-cm (95% C.L.). This represents a factor of 5 improvement over the previous best limit on the muon EDM.