Can anyone recommend a good book to get started with AI programming. A non language specific book that concentrates on the theory would be best. But any book will do.

Try Tom Mitchell's book "Machine Learning" I think it is a great book that covers many aspects of modern AI. Be forewarned it is not traditional AI (like A-Star) but more bayes and Neural Network techniques.

If you want a good comprehensive overview of AI techniques, you want "Artificial Intelligence - A Modern Approach" by Stuart Russell and Peter Norvig. It covers pretty much every topic you can think of in AI; decision trees, Bayesian logic, Fuzzy Logic, Neural Networks, Genetic Algorithms, A* search, knowledge representation, planning, resolution, min-max, alpha-beta and more... There's plenty of pseudo-code and in-depth theory coverage as well.

It's the text used for the fourth year "Applied AI" course in Carleton University's Cognitive Science program... If you really want to get "into" AI, I would recommend this book.