An Introduction to Bioinformatics Algorithms. Neil C. Jones and Pavel A. Pevzner

Building bioinformatics solutions with Perl, R and MySQL.

extremely readable with some good code. not solely programming focused (considerable conceptual descriptions of problems/solutions and also, as you would expect from the title, some statistics/numerical data manipulation in R).

When I got started I found a copy of David Cross's Data Munging with Perl helpful. Contains several good command line solutions to common problems.

Not a book, but the online tutorials for database programming at Perlmonks are also pretty good.

I also liked the Building Bioinformatics Solutions book (mentioned by @occam) -- at the time it came out it was one of the few books that demonstrated concisely how various open-source tools can be put together into a workflow.

More specific answers will depend on what you want to use Perl for -- data handling, algorithm development for some task, web-based development, etc..

Try to solve the problems(if possible programatically) in Durbin, Eddy, Krogh's book. If you get stuck consult the solutions manual

I like Data Mining: Practical Machine Learning Tools and Techniques by Witten, Frank and Hall. From the Amazon description, Data Mining "offers a thorough grounding in machine learning concepts as well as practical advice on applying machine learning tools and techniques in real-world data mining situations". And, it works together with the excellent (Java based) Weka machine learning software. Good for beginners and advanced users alike.

You might also find some useful books in related questions here, here and here.