I'm learning Objective-C at the moment (although I used to programme in BBC Basic and later Blitz Basic on an Amiga as a kid, and did some Pascal a few years ago, so wasn't necessarily starting totally from first principles). I am aiming to get into iOS coding, but currently I've just completed the Apress book 'Learn C on the Mac' and now I'm working through the sequel, 'Learn Objective-C on the Mac'. There is then a third book that takes you on to Cocoa and iOS development, building on what you learn in the first two.
That's the route I've chosen, and I have so far found these books really enjoyable and at exactly the right level for me, but you might need to look around to get the right ones for you.
What people are saying is right - time and patience are the most important things. I would add though - you should pick a book you like the look of, but as you go, just try and have fun with coding, messing about and trying different things as you go.
The 'Learn C on the Mac' book had exercises at the end of every chapter (usually write a programme or alter a programme type of exercise), and I always made sure I completed and understood those, but the follow up Objective-C book has no exercises at all.
Therefore, I always make sure I write a little programme or alter the one I did for the chapter before (if that's more appropriate) before I move on to the next chapter. I find this really fun, and it always makes sure that I have understood the concepts.
Practice makes perfect and that's what it's all about. Reading the right books AND messing about and enjoying coding just for the hell of it will make sure you make good progress. If you find you don't enjoy messing about with code, then it probably isn't for you.