There are basically two cases I work with for subroutines:

1. Methods in a class
2. Subroutines in the actual program (often calling a centralized class)

For the first, I always document everything with POD, except for private data. I think that someone using an object should never have to look at the actual source code, so it has to be documented, no matter how trivial.

Subroutines in a program are different. If someone wants to use those, they have to be digging through the source anyway. Most of the programs I write are CGIs, and go through a simple set of subroutines almost every time (set parameters, validate parameters, read or write a database, print the results or an error message). The subroutines that do this job are given obvious names (set_params, validate, read_db/write_db, print_results). It seems silly to document these with a subroutine header. However, a CGI that needs something beyond this will have its additional subroutines documented.