Well, my advice is minor as I am just starting out, but I was a math and physics undergrad and am now a grad student in Machine Vision/AI. This is what I have learned on my first year for intro material. Although, keep in mind, most of my work is very mathematical and not necessarily what you will see in most AI research (I do a lot of curve matching). One thing I have learned is that there is A LOT of A.I. fields and there are very different things you will need to know for each of the fields. Here are the things that I have found interesting and useful:
Books
--------------
Structure and Interpretation of Computer Programming by Abelson and Sussman (even if you don't use scheme or lisp, it will help you think)
Artificial Intelligence: Norvig (good intro)
Algorithms: Cormen
Anything by Knuth (beware! This stuff is insanely crazy for someone starting out. But the dry humor makes it easy to read none the less. He rates problems by how hard they are. A level 4 (or possibly 5, I forget) are research problems that he warns can take a while. The first level 4 problem was Fermat's last Theorem. I'm hoping that was a joke.)
Lectures
--------------
Lectures for computer science are everywhere and open. It is a good field to find free lectures and textbooks. I'm sure you can find them other places, but iTunes U has most of these.
MIT:
a) SICP lectures by Sussman and Abelson (old but still good, these are on the web but not iTunes
b) Algorithms (on iTunes)
Stanford
a) 106a (if you know a lot can probably be skipped. But if you don't have formal training in programming. I'd still go through it to learn about style a bit better)
b) 106b (beginning abstractions. Coming from physics you will probably need this. I know I did)
c) 107 (awesome!)
d) Machine Learning (I forget the number, but I'm sure this is what you want.)
Berkeley:
The freshman sequence is on iTunes. Scheme, Data Structures and Architecture
Interesting people to look up on youtube or Video.google are Gerald Sussman, Marvin Minsky, John McCarthy, Donald Knuth, and the company Novamente had a good Google talk on artificial general intelligence. There wasn't a lot of substantial information, but it was entertaining.
But the way that I would start is with SICP, and the lectures that go with it (Berkeley's first course, Stanfords 106a/b and MIT's SICP lectures all together. You will come out with familiarity in scheme, C, and Java, which is good) Then I would move on to data structures and algorithms. You may think you are a good programmer, but these courses will help make sure that you are. Best of all, SICP is free online. So, you can't go wrong starting with that. Plus, you get free lectures that go with it.
http://mitpress.mit.edu/sicp/
And since you are a physicist (structure and interpretation of classical mechanics)
http://mitpress.mit.edu/SICM/
But the best advice on how to start I can give is to have fun!