Categorical data is widely available in many real-world applications, and to discover valuable patterns in such data by clustering is of great importance. However, the lack of a decent quantitative relationship among categorical values makes traditional clustering approaches, which are usually developed for numerical data, perform poorly on categorical datasets. To solve this problem and boost the performance of clustering for categorical data, we propose a novel fuzzy clustering model in this paper. At first, by approximating the Maximum A Posteriori (MAP) estimation of a discrete distribution of data partition, a new fuzzy clustering objective function is designed for categorical data. The Bayesian dissimilarity measure is formulated in this objective to tackle the subtle relationships between categorical values efficiently. Then, to further enhance the performance of clustering, a novel Kullback-Leibler (KL) divergence-based graph regularization is integrated into the clustering objective to exploit the prior knowledge on datasets, for example, the information about correlations of data points. The proposed model is solved by the alternative optimization and the experimental results on the synthetic and real-world datasets show that it outperforms the classical and relevant state-of-the-art algorithms. We also present the parameter analysis of our approach, and conduct a comprehensive study on the effectiveness of the Bayesian dissimilarity measure and the KL divergence-based graph regularization.