What do we mean when we say that an approach is "Bayesian"? I'm trying to explain to a nontechnical colleague of mine what a Bayesian approach is. I realized that despite having used Bayesian methods on more than one occasion in the past, I don't have an intuitive definition of what makes an approach Bayesian or not. 
Based on several definitions I've seen in textbooks and online resources, the term "Bayesian" seems to mean: 
Choosing a prior model, and then updating this prior model with new empirical data to obtain an improved posterior model. 
This comes from applying Bayes rule to the context of modeling: 
$P(Model\: |\: Data) \propto P(Data\: |\: Model) \:P(Model)$
But then isn't this just the definition of supervised machine learning in general? 
What makes an approach specifically Bayesian and not just supervised learning? Or is it the case that all supervised learning really boils down to an application of Bayes rule? 
 A: Non-Bayesian methods may be non-probabilistic, or they may define a probability distribution on the data that depends on some fixed (but perhaps unknown) parameters. Bayesian methods are distinct in that they use probability distributions to express knowledge/uncertainty about both the data and the model/parameters.
In a Bayesian approach, we can think of the data as having been drawn from some probability distribution. But, we don't know know which one. To express this uncertainty, we consider a set of possible data-generating distributions. We then define a distribution over these possibilities, which represents our degree of belief in each. Before we see the data, this distribution is called the prior, and it represents our pre-existing knowledge about the problem. After seeing the data, we update this distribution using Bayes' rule, then call it the posterior.

But then isn't this just the definition of supervised machine learning in general?

As above, supervised learning need not be Bayesian. For example, we may learn the parameters of a classifier, but not consider a distribution over many possible classifiers. Even if we fit many classifiers (as in ensemble methods), we need not treat this as a probability distribution, or update it using Bayes' rule. And, as Peter Flom pointed out, Bayesian methods are not limited to supervised learning.
A: For one thing, "Bayesian" doesn't only apply to supervised learning. Any time there is a hypothesis test in frequentist statistics, there can be a Bayesian approach. 
Also, I would say that Bayesianism is more than just choosing a model and then updating it, although it depends on what you mean by "choosing a model". In a Bayesian approach you choose a prior probability.  So, for instance, saying "let's use linear regression" could be regarded as "choosing a model".  To make it Bayesian, you'd have to add a prior. 
A: Bayesian and frequentist frameworks have difference conceptions of the nature of probability. In the Bayesian world the stuff of probability is partial belief and in the frequentist world probability is made of long-run frequencies.
The distinction may have fewer practical consequences than might at first be thought, because when beliefs are rationally formed by unbiassed agents the expected long-run frequencies correspond closely enough to the frequentist ideals, and in many circumstances the long run frequencies allow at least a rough and ready state of partial belief that mimics that of a Bayesian.
