If you are completely new to programming take a look at How to Think Like a Computer Scientist. It seems quite good, and starts at the very beginning. It is also available on-line, so you don’t have to run to the bookstore and fork out $$$.
It teaches Python, which I think is a good beginner language. It also teaches programming in general, and you will find that what you learn will help you later if you want to learn other languages. Many people will tell you a lot about which programming language is the best first programming language. I don’t think it matters much really. What is more important is to learn one language and to learn it well.
Of course, there are a lot of other good resources as well. It’s good to have access to as many as possible. Each one will have its strengths and drawbacks.
Once you have got a good understanding of the basics, I recommend Dive Into Python which is also available in the Debian repositories (aptitude install diveintopython).