Quantile regression captures the relationship between covariates and the conditional response distribution as a whole, rather than the expected value of the conditional response distribution as in linear regression. However, there are no widely accepted quantile regression methods for ordinal variables, despite the broad use of this form of data in health and medical contexts. We introduce a new method, Bayesian Ordinal Quantile Regression with a Partially Collapsed Gibbs Sampler (BORPS), for quantile regression with ordinal responses. We develop a fast, efficient Gibbs sampler for BORPS. Through an extensive set of simulations, we demonstrate superior results to the two existing ordinal quantile regression methods. We then apply BORPS to study the drivers of early puberty, a strong indicator of future health problems. Previous work in this area has been limited by the ordinal nature of data on puberty stages, as well as the fact that associations at the extreme quantiles are more informative than those at the expected value. We address these limitations by applying BORPS to the Fragile Families and Child Wellbeing dataset, and we identify important risk factors for early puberty.