I've read O'Reilly's Collective Intelligence. It's a great introductory survey, but it was very light on theory.
I also own Collective Intelligence in Action. It had more explanation of theory than O'Reilly's offering, but most of the chapters devolved into how to use Java data mining framework X.
- Machine Learning by Tom M Mitchell http://www.cs.cmu.edu/~tom/mlbook.html
For general reading and introductions I also like:
- Pattern Classification by Richard Duda
- Pattern Recognition and Machine Learning by Christopher Bishop
For a bit more emphasis on statistics and math, I usually dive in to
- Classification,Parameter Estimation and State Estimation by van der Heijden
And last, but certainly not least:
- Information Theory, Inference, and Learning Algorithms by David MacKay, available here:
http://www.inference.phy.cam.ac.uk/mackay/itila/