Approximate inference by sampling from an appropriately constructed posterior has recently seen a dramatic increase in popularity in both the robotics and computer vision community. I will describe a number of approaches in which we have used Sequential Monte Carlo methods and Markov chain Monte Carlo sampling to solve a variety of difficult and challenging inference problems. Very recently, we have also used sampling over variable dimension state spaces to perform automatic model selection. I will present two examples of this, one in the domain of computer vision, the other in mobile robotics. In both cases Rao-Blackwellization was used to integrate out the variable dimension-part of the state space, and hence the sampling was done purely over the (combinatorially large) space of different models.