Absolute Java (6th Edition) by Walter Savitch. (Highly recommended. This book walks the reader through Java at a reasonably slow pace.)
Head-First Design Patterns by Eric Freeman, Bert Bates, Kathy Sierra and Elisabeth Robson. (An easy-going and fun introduction to design patterns with examples in Java.)
Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides. (The standard reference for object-oriented design patterns.)
How to Design Programs (Second Edition) by Felleisen, Findler, Flatt, and Krishnamurthi. Draft, 2010.
How to Design Classes by Felleisen, Findler, Flatt, Gray, Krishnamurthi, and Proulx. Draft, 2008.