We introduce a general Bayesian framework for graph matching grounded in a new theory of \emph{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 probabilistic objects. A novel sequential metaphor, the \emph{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 centered on permutations. As an application, we develop a Bayesian model for graph matching that integrates a correlated stochastic block model with our novel class of priors. The cycle structure of the matching is linked to latent node partitions that explain connectivity patterns, an assumption consistent with the homogeneity requirement underlying the graph matching task itself. Posterior inference is performed through a node-wise blocked Gibbs sampler directly enabled by the proposed sequential construction. To summarize posterior uncertainty, we introduce \emph{perSALSO}, an adaptation of SALSO 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.