Hurricanes are one of the most extreme storm systems that occur on Earth, characterized by strong rainfall and fast winds. The terrestrial exoplanets that will be characterized with future infrared space telescopes orbit M dwarf stars. As a result, the best observable terrestrial exoplanets have vastly different climates than Earth, with a large dayside-to-nightside irradiation contrast and relatively slow rotation. Hurricanes may affect future observations of terrestrial exoplanets because they enhance the vertical transport of water vapor and could influence ocean heat transport. In this work, we explore how the environment of terrestrial exoplanets orbiting M dwarf stars affects the favorability of hurricane genesis (formation). To do so, we apply metrics developed to understand hurricane genesis on Earth to three-dimensional climate models of ocean-covered exoplanets orbiting M dwarf stars. We find that hurricane genesis is most favorable on intermediate-rotating tidally locked terrestrial exoplanets with rotation periods of $\sim 8-10~\mathrm{days}$. As a result, hurricane genesis is most favorable for terrestrial exoplanets in the habitable zones of late-type M dwarf stars. The peak in the favorability of hurricane genesis at intermediate rotation occurs because sufficient spin is required for hurricane genesis, but the vertical wind shear on fast-rotating terrestrial exoplanets disrupts hurricane genesis. We find that hurricane genesis is less favorable on slowly rotating terrestrial exoplanets, which agrees with previous work. Future work using simulations that resolve hurricane genesis and evolution can test our expectations for how the environment affects the favorability of hurricane genesis on tidally locked terrestrial exoplanets.