The median is a simple and meaningful measure for the center of a long-tailed survival distribution. To examine the covariate effects on survival, a natural alternative to the usual mean regression model is to regress the median of the failure time variable or a transformation thereof on the covariates. In this article we propose semiparametric procedures to make inferences for such median regression models with possibly censored observations. Our proposals can be implemented efficiently using a simulated annealing algorithm. Numerical studies are conducted to show the advantage of the new procedures over some recently developed methods for the accelerated failure time model, a special type of mean regression models in the survival analysis. The proposals discussed in the article are illustrated with a lung cancer data set.