All the forms are commonly used:, it probably depends rather on each writer's personal style and on the style guide of the publisher of the text where the phrase appeared.
Bayes is always capitalized since it is a surname.
"naive" is or is not capitalized depending on a writer's style. It could be capitalized if a writer capitalizes all names of methods (e.g. Tom Michell, quoted by you, seems to capitalize also "Maximum a Posteriori", or "Maximum Likelihood Estimation"). It could be lowercase if all names are written lowercase (see similar example of distributions names). "Naïve" is just a alternative spelling for "naive" so it is just a question of spelling convention used by the writer.
See also https://english.stackexchange.com/questions/14/which-words-in-a-title-should-be-capitalized and https://english.stackexchange.com/questions/6560/when-should-you-use-title-case