The new Muon g-2 experiment at Fermilab, while primarily designed to measure the muon's anomalous magnetic moment, also offers the unique opportunity to perform a world-leading search for the muon's electric dipole moment (EDM). Within the Standard Model, the muon EDM is predicted to be vanishingly small, orders of magnitude smaller than the reach of current experiments. However, some BSM models predict different mass scaling, or decouple the EDM from the lepton masses altogether, allowing for much larger EDMs. As such, any observed signal would provide direct evidence of new physics and a new source of CP violation in the lepton sector. Even in the absence of a discovery, improving the experimental limits on the muon EDM provides valuable constraints on BSM theories. This talk will present the experimental strategies employed at Fermilab to search for a muon EDM, with a focus on using data from the straw trackers, and will give an update on the current status and future prospects of the analysis.