I've browsed through a friends copy of Learning Perl, and it seemed almost counter-intuitive for a non-programmer such as myself.
In that case, you should probably start by learning to program first. Learning Perl is a very simple textbook on Perl, but is probably not the ideal resource for someone who doesn't even know how to program! I am not sure if there are any Perl-books designed for non-programmers, maybe some "dummies", "teach yourself in 21 days", or simililar book will help you, but in my opinion you would be better suited with a book designed for use in an introductory programming course in a university.
Once you know how to program, I think you will find "learning Perl" comprehensible. I am not aware of any Perl books designed for teaching people how to program, so you may have to take a detour and learn some other language first.
Which language you choose will not matter much in the end, as it is the general programming concepts that is important, and not specific language details. Since you seem to be doing this on your own, and not participating in a class, it would be an advantage to choose a widely used language, as it will probably be much easier to get help that way.
While some less used languages, such as Scheme, ML, Haskell, Prolog and others are perfectly suited for teaching introductory programming classes, it might be harder to keep yourself inspired if you feel you are the only one in the world working with that language (that will not be true, of course, but it can feel that way). On the other hand, people actually using (as opposed to learning) them are often very knowledgeable of computer science.
I recommend you start with a good text-book on Java, as it is a relatively clean language, that happens to be pretty popular for the time being. And it also has good standardized class libraries for GUI-programming and other stuff that can be inspiring to use.
Another good choice would be C, because if you want to do programming, at some point in time you will probably have to learn it anyway. But C is a bit more difficult to learn than Java, so it's perhaps not the best choice.
I can also recommend Python, which has some excellent introductory tutorials aimed at non-programmers, a relatively clean syntax, and otherwise many of the same features as Perl. On the other hand, I don't know of any books aimed at complete beginners in Python either, but it might be easier anyway.
Delphi might also be a good option if you are working on Windows, but since you ask about Perl, you are probably not?
Perl and C++ is examples of programming languages that both have lots of good features. However, both languages are so big and complex that a total beginner will become overloaded with details, so they are probably not ideal choices.
Note that there are many crappy textbooks, as well as some good ones. Since I haven't read many introductory textbooks lately, I will not recommend any, but you will find recommendations many places on the web (such as amazon.com customer reviews). The best way to find out is perhaps to go to a university bookstore and ask (not nessecary those who work there, but perhaps the guy with the glasses looking out obscure books who has been there for hours). Make sure that you get a book meant for people with no prior programming knowledge, not just an introductory tutorial for people wanting to learn a new language.