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.