The cool thing about programming is that once you create a foundation, you can use it to expand out and understand other languages. It's not like say an actual spoken language where one may be completely different from the other. That's not to say that there aren't differences, but programming is all about the underlying concepts -- understand those and you'll be able to learn just about anything. This is why its common for many programmers to be fluent in multiple programming languages.
As far as starting out with Perl...I'm a little reluctant to suggest it. I'm working on teaching myself programming, so I spent time researching avenues. There is some very good advice in this thread. You really should first figure out what it is you want to program - IE: are you looking for desktop apps or web apps? In the case of Perl, you're really going to be running web apps. So answer that question first. As others have said, the free book is nice, but Perl is complex and not exactly the best language to start out with.
Personally speaking, I would suggest the usual C/C++, Java, PHP, Python, Ruby route. Another potential candidate is VB.NET, which I'm currently learning. And last but not least, you have the other option of going with something even more basic. The Dummies series makes a good Beginning Programming book. It's pretty cheap and it uses very basic languages (non pun intended -- including Basic) that teach fundamentals. That really breaks it down to what I was talking about earlier with the foundation.
I hope all of that helps you out a bit, let me know if I can be of help.