  Dark matter substructure, such as primordial black holes (PBHs) and axion
miniclusters, can induce phase shifts in pulsar timing arrays (PTAs) due to
gravitational effects. In order to gain a more realistic forecast for the
detectability of such models of dark matter with PTAs, we propose a Bayesian
inference framework to search for phase shifts generated by PBHs and perform
the analysis on mock PTA data with the software \texttt{enterprise}. For most
PBH masses the constraints on the dark matter abundance agree with previous
(frequentist) analyses (without mock data) to $\mathcal{O}(1)$ factors. This
further motivates a dedicated search for PBHs (and dense small scale
structures) in the mass range from $10^{-8}\,M_{\odot}$ to well above
$10^2\,M_{\odot}$ with the Square Kilometer Array. Moreover, with a more
optimistic set of timing parameters, future PTAs are predicted to constrain
PBHs down to $10^{-11}\,M_{\odot}$. Lastly, we discuss the impact of
backgrounds, such as Supermassive Black Hole Mergers, on detection prospects,
suggesting a future program to separate a dark matter signal from other
astrophysical sources.
