If you've not come across them already take a look at Test::Simple, Test::More and Test::Tutorial.

You might also find Test::Class of interest (but since I wrote that one I may be biased :-)

As to what you test - I tend to write all my code "Test First". Basically this means:

1. I write the test for what I want my code to do.
   This (of course) fails since there isn't any code yet.
2. I then write code until my test passes.
3. Then, since I know I've finished and can move along to the next piece of functionality that needs testing.

Works very well for me. I get into the coding "flow" much faster this way and end up with very robust code.

Test suites also make changing your code a much less stressful business since you immediately know if you've broken anything.

I always have a window open that sits there doing a make test every time any file in my project changes. Instant feedback. Very handy.

This style comes from Extreme Programming (also known as XP - just be be confusing). If you're interested take a look at extremeprogramming.org.

Retrofitting a test suite on an existing code base can be a much more painful task. Two approaches that have worked for me are:

1. Testing the documentation (Test::Tutorial has an example of this).
2. Write tests for any bit of code that you need to change. That way you can check that you don't break anything as you make the change, and you will gradually build up a set of tests for the whole code base.