We introduce a general Bayesian framework for graph matching grounded in a new theory of exchangeable random permutations. Leveraging the cycle representation of permutations and the literature on exchangeable random partitions, we define, characterize, and study the structural and predictive properties of these distributions. A novel sequential metaphor—the position-aware generalized Chinese restaurant process—provides a constructive foundation for this theory and supports practical algorithmic design. Exchangeable random permutations offer flexible priors for a wide range of inferential problems where the parameter of interest is a permutation, including statistical graph matching and unmatched regression. As an application, we develop a Bayesian model for graph matching that integrates a correlated stochastic block model with an edge-discrepancy likelihood. The cycle structure of the matching permutation is linked to latent node partitions that explain connectivity patterns—an assumption consistent with the homogeneity requirement underlying the graph matching task itself. This structural alignment not only grounds the model statistically but also enhances the mixing behavior of the sampling algorithm. Posterior inference is performed through a node-wise blocked Gibbs sampler directly inspired by the proposed sequential construction, allowing coherent updates in the complex permutation space. To summarize posterior uncertainty, we introduce perSALSO, an adaptation of the SALSO algorithm to the permutation domain that provides principled point estimation and interpretable posterior summaries. Together, these contributions establish a unified probabilistic framework for modeling, inference, and uncertainty quantification over permutations.