The Elements of Statistical Learning together with the online course (http://www.r-bloggers.com/in-depth-introduction-to-machine-l...) makes for a great introduction.

EDIT: Oops I should have said "An Introduction to Statistical Learning with Applications in R" rather than The Elements of Statistical Learning. The Elements book goes into way too much depth to be a good introduction to the subject.

Similarly, An Introduction to Statistical Learning With Applications in R is like a practical version of (or companion to) Elements. I very much enjoyed it.

And the Stanford version of the same class linked above for ISLR is, in my opinion, better:

https://lagunita.stanford.edu/courses/HumanitiesandScience/S...

Yes good point, my bad - I meant to link to "An Introduction" rather than "Elements". Elements is not a good starting point - your head will explode.

Depends on what you want to learn.