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.