Starting step-by-step is a good approach. When I started, I focused on working with files and applying regular expressions to extract relevant information. And I didn't bother much that all my control-structures looked like c. Afterward I played with hashes and then with Win::OLE and Excel - just because that were the things I needed most.

A great way to learn is also the monastery: I often use the questions by other monks as a challenge to produce some working code. And afterward I compare my solution with the highly optimized ones of the more experienced monks here. And try to understand their solutions. I think I learned very much that way. And if I look at (perfectly working!) code I wrote some months ago, I see a huge difference in style and efficiency. :-)

If you want a collection of good exercises and other information for a beginner, you may also have a look at the following great collection by planetscape: Re: Real Life Perl Exercises.