The one piece of advice I can give you, jeno, is that no one should teach themselves programming. It's a bad way to get started.
Absolute nonsense. I taught myself BASIC at 12, C at 14 and have been hacking at various projects in various languages ever since. If I could do it then, anybody can learn to program on their own. It just requires determination and perseverance.
As for a good book on learning to programming for Mac OS X, that is pretty tough. I've taught comp sci at university for a few years, and my personal experience tells me that if you're not familiar with basic concepts of programming (i.e. conditional statements, loops, function calls, etc), you're probably better off learning the basics before jumping into Cocoa. To do that, I would suggest picking up an introductory book on the 'C' language. I'd recommend a book like
this. Don't let the title fool you. You are not going to learn to program in 'C' in 24 hours. What it means is that the book is divided into 24 chapters, each chapter should take you 1 hour to read and to
do the exercises. Once you've read a chapter and done the exercises, look at the answers provided. I really really recommend that book as it is the closest you can get to being taught in a class, without actually having to attend a class. If you're casual, set aside 1 hour a day and you'll be proficient in 'C' within a month.
Once you know 'C', you can then start to look at Mac OS X programming. I'd suggest going learning to program with Cocoa. A good good book for this is
Cocoa Programming for Mac OS X. Nailing down Cocoa will take considerably longer than learning 'C', but you will definitely have more fun since the projects you work with are going to be graphical in nature.
Programming is a very hands on practical thing. As with all practical things, you get better by practice and not by merely reading books (though they help!). Get a good book, read it, practice and come back to ask questions.