From what I read the Theil-Sen estimator seems to be a really cool estimator; robust and easy to understand. Would it be possible to device (or does it already exists) a Bayesian "version" of the Theil-Sen estimator so that you provide a prior for the slope and get a probability density back instead of just a point estimate? How would such an estimator look/work?
According to the Complete Class Theorem proved by Abraham Wald in his book "Statistical Decision Functions", an estimator is admissible if and only if it is Bayes for some prior. Hence, if the Theil-Sen estimator can't be obtained as a Bayes decision, it is inadimissible.
Since the Theil-Sen thingy is robust to outliers by virtue of dealing with medians, I guess the natural Bayesian regression model is one with a t-distribution with unknown degrees of freedom (or other fat tailed distribution, e.g. double exponential might be closest in spirit) replacing the normal distribution of classical regression.
In this case the prior for the slope is not so important because fatter tails for Y allow occasional outliers without affecting the slope estimate. The degrees of freedom in the relevant t is, in a complete analysis, marginalised out of the joint posterior.
Some discussion of this class of models can be found in chapter 14 and 17 of Gelman's Bayesian Data Analysis. A choice of distributions is explored in chapter 8 (stacks) of the BUGS Examples Volume one.