Elements Of Statistical Learning: now free pdf
www-stat.stanford.edu
www-stat.stanford.edu
I haven't read it, but this comparison has convinced me of its worth.
Hastie is more of a statistical approach with statistical rigor.
McKay's looks like a good book, but appears more applicable to pure information theory rather than ML specifically.
That said, it is meant for people who are comfortable with math/stats; its much more statistics oriented than, say, Mitchell's book. But they do a good job of explaining things in non-math language. This book does a good job of exposing high level ML concepts (e.g. bias-variance tradeoff) but still teaches a lot of the standard methods & tools.
These are actually two of my favorite books on the subject and I can't recommend them both enough.
Their names are pretty catchy; I'll admit I want to use 'gradient boosting' and 'Lasso and elastic-net regularized generalized linear models'.
http://www.amazon.com/Principles-Statistics-M-G-Bulmer/dp/04...
It's kind of old, but it helped me a lot...
Edit: It's also on Google Books, if you want to take a look
The visualizations are very nice.
Looks like a very useful text.
http://www.autonlab.org/tutorials/
Probability for Data Miners, for example, has much of the basic math you need for machine learning algorithms, for example.