I own 91 books covering iPhone app programming, design, marketing, and business, and I've browsed plenty more. From all those books I've picked out the ones I consider to be the very best. My recommendations are split into four parts:
Learning iOS Programming (below)
Part 1 - Learning iOS Programming
Learning to program the iPhone & iPad has never been easier due to some fabulous books. Programmers who are new to Apple have to learn Apple's Cocoa Touch SDK and in most cases will be learning Objective-C as a new programming language too. Of the 21 iphone programming books I've read, here are the best...
I recommend you start with Beginning iPhone 3 Development – Exploring the iPhone SDK (soon to be updated to 'Beginning iPhone 4 Development'). Jeff LaMarche and Dave Mark clearly introduce and explain the most important topics to get new iOS developers over the initial steep learning curve. Of all the iPhone books this remains the best for developers new to iOS. They have a companion book 'More iPhone 3 Development', but you won't need that unless you later want to delve into advanced topics.
Another great book for learning iOS programming is iPhone Programming: The Big Nerd Ranch Guide by Joe Conway and Aaron Hillegass. This books is written by the premier iOS and Mac training company in the world. It covers more topics than Beginning iPhone 3 Development, but it still starts out slow and easy, has a lot of great explanations of 'good ways to do it' and it includes introductions to Apples iOS development tools too, so you get a very well rounded kick start on the platform. Because it covers so many topics it makes a good reference later for stuff you forget.
If you like books with lots of text to explain stuff, you should start with 'Beginning iPhone 3 Development' if you hate lots of text and really just prefer short lessons on 'how to do it on iOS' then start with the Big Nerd Ranch book. But people, this stuff is really difficult when you first start, so its worth having both so you can hear two different voices when you get stuck.
Once you start writing your first app you'll find there are lots of little specific things to figure out, your best bet is to check with Erica Sadun first by looking in the pages of her wonderful book 'The iPhone Developer's Cookbook'. Its a great companion for any iOS developer, and its the one book I refer back to most often.
Programming for iPhone means programming in Objective-C. Objective-C is the C language, with dynamic object oriented extensions. Coming from any other language, you'll need to learn the Objective-C way, and for that you should check out ‘Learn Objective-C on the Mac', though there are a bunch of newer Objective-C books I've not seen (if you find one you love, let me know). Also consider adding 'Programming in Objective-C' by Steve Kochan to your library, as this is the comprehensive language reference, it will have the answer when you are trying to figure out more complicated parts of the language. Some of the more advanced parts of iOS development, eg audio processing, are done in C rather than Objective-C. This means that when you get to those you'll need to understand the crazy C stuff of pointers to pointers to functions returning references to arrays of pointers to alloced memory buffers... If all those stars and ampersands get you down you should go back to an easy learning C book, of which there are many, eg ‘Learn C on the Mac'.