  Dark matter substructure, such as primordial black holes (PBHs) and axion
miniclusters, can induce phase shifts in pulsar timing arrays (PTAs)
measurements 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. 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.
