Gravitational observables, particularly those which might be detected by high precision timing measurements like those made in pulsar timing arrays, present a compelling opportunity to detect dark matter through its only known coupling to matter. However, the mechanisms which result in observable signals are often challenging to characterize, particularly at the level of their statistical properties sufficient to design sensitive analysis methods and reach optimal detection sensitivities. In this talk, I will discuss these challenges and opportunities in the context of searches for ultralight dark matter and searches for dark matter substructure using data collected by pulsar timing arrays.