We study $k$-divisible partition structures, which are families of random set partitions whose block sizes are divisible by an integer $k=1,2,\ldots$. In this setting, exchangeability corresponds to the usual invariance under relabeling by arbitrary permutations; however, for $k>1$, the ordinary deletion maps on partitions no longer preserve divisibility, and so a random deletion procedure is needed to obtain a partition structure. We describe explicit Chinese restaurant-type seating rules for generating families of exchangeable $k$-divisible partitions that are consistent under random deletion. We further introduce the notion of {\em Markovian partition structures}, which are ensembles of exchangeable Markov chains on $k$-divisible partitions that are consistent under a random process of {\em Markovian deletion}. The Markov chains we study are reversible and refine the class of Markov chains introduced in {\em J.\ Appl.\ Probab.}~{\bf48}(3):778--791.