I'm surprised nobody has mentioned Learning Perl. Full of great exercises. The exercises are not overly simple, but should take less than an hour to complete. Perfect intro to the language, and programming in general. It's also written in a more relaxed style that will be less intimidating to a high school student than something like Knuth.

Once you feel like they've got the basics down, maybe check out Intermediate Perl (which also has great exercises). It is hard sometimes as a novice programmer to see how all of those basic skills can be put together to make something interesting besides just adding numbers and printing the result. This book bridges the gap well.

Also, given the amount of time that kids spend on the internet nowadays, I'd recommend showing them some of the stuff out of a book like Spidering Hacks, or Perl & LWP. This might stimulate their interest, and is something they can actually use in their day-to-day lives. Maybe have them write a program automatically check for any new posts on a few of their friends blogs/myspace pages/livejournals/etc.

I think these types of exercises work much better than abstract simple exercises such as "Write a program for the factorial of a number...",etc. These sort of exercises bore the hell out of a kid, who'd rather be blasting aliens in Halo 7 than writing trivial scripts for math problems on a computer. Try to find something that they can relate to, and apply to make something they enjoy easier.

Maybe give them an open assignment, like "Take a task you do everyday on the internet, and automate it using Perl." Kids have very creative minds, and I wouldn't be surprised if some of your students came up with something that hasn't been thought up yet.

---mmmmtmmmm