Cryptography can be a difficult subject to learn. Until recently, there were only a few books available and, even now, most of them aren't well-suited to self-study for anyone who doesn't already have a strong math background. Cryptography is a mathematical field. If you want to be cryptographer, you will have to learn probability, number theory, abstract algebra, etc. But, those aren't strict prerequisites to learning basic cryptography so you can study those areas as you go along.
I became interested in cryptography in the late 1990s after reading Schneier's Applied Cryptography, but I had other interests, responsibilities, etc. so I never went very far with it. Recently, I've been trying to take my skills to a higher level and I've found several resources that are helpful to me. Those are outlined here.
My favorite introductory text is Understanding Cryptography by Christof Paar and Jan Pelzl. The book is readable and doesn't assume a math background beyond about the algebra/pre-calculus level. The authors explain basic concepts in abstract algebra and number theory as needed. The book has a companion website here.
Last week, I signed up for a free cryptography course at Coursera written by Dan Boneh. I don't have an opinion on it yet, but I'll update this post when I do. The sequel course starts in January and if I like the first one, I'll sign up for that too. I don't expect much of what the course covers to be new to me, but I'll be happy to pick up anything or even just to hammer away some misconceptions.
After learning the basics, things open up a bit. For learning more about block ciphers, I highly recommend The Block Cipher Companion by Lars Knudsen and Matthew Robshaw. Bruce Schneier also wrote a self-study course on block cipher cryptanalysis. Most of the ciphers listed in the "Basic Cryptanalysis" section are pretty easy to break; if you can't break some of those you have no future as a code breaker. All of the ciphers after that are published or real-world ciphers and the breaks are much harder to find. My guess is that most people won't be able to break any of them early on. Still, it provides a guide to the pre-AES literature on cryptanalysis. I also recommend Howard Heys' tutorial on linear and differential cryptanalysis; it's easy to understand and provides a better introduction than most books.
Many of the problems that crop up in the real-world are due to implementation flaws or bad protocols. AES may be secure, but if you're implementing it in ECB mode with keys that are based on the time of day, you're doing things very, very wrong. If you plan to implement cryptographic algorithms and/or protocols in the future, start with the book Cryptography Engineering and start reading Matthew Green's blog on the same subject.
Nate Lawson blogged about intermediate cryptography resources last year. The post is short and has several links. Just read it.
If you're hoping to move further in cryptography, you may want to check out Nigel Smart's posting about prospective Ph.D. students. Smart outlines the skills that he expects in prospective students depending on whether their background is in CS or mathematics. The cryptography group at the University of Bristol also has a list of 52 Things People Should Know to Do Cryptography. The list is targeted at first-year graduate students and includes topics from computer science and engineering, mathematics, and cryptography.
Nate Lawson and the 52 Things list both recommend Nigel Smart's book which is freely available online. I just started reading it and will update this blog post in the future if I have anything meaningful to say about it.
Edit: I can't believe I forgot the Handbook of Applied Cryptography! It's not a very easy read so I don't recommend it as a standalone text, (for a beginner) but it's an excellent reference. Download it and/or save the link so you can reference it as needed.