How to Design Programs is awesome, but really very slow and pedestrian later. Feel free to either skim or switch to another book once you outgrow it.
Definitely, do all the exercises in any programming book you are trying to learn from. In some sense, the exercises are the meat of any such book, and the rest is just supporting material.
Some people even start a new chapter with a look at the end-of-chapter exercises, try their hands at them for a few minutes. They'll most likely fail, but one gets a better perspective of what to watch out for in the chapter.
Yeah, in a certain sense it's a lot like mathematics. You try your hand, perhaps you get it right the first time, more often than not you don't but at least you learn something out of it.
I've been teaching a bit, and what worked was to start with Racket on How to Design Programs (http://www.ccs.neu.edu/home/matthias/HtDP2e/part_prologue.ht...) for a while and then switch over to Haskell material, like Learn You a Haskell.
Racket is a great language too in itself, and has terrific material for beginners.