I admit to being extremely shallow, and looking first and last at the API. Not only am I interested in whether or not the API makes sense to me, I also favour modules that can be programmed in my favourite coding style. Everyone has their own style, and sometimes if there is a selection of different modules doing similar things I try to find one which best matches me - it seems to be a good way of achieving karmic balance in your programming :-)

Another thing I sometimes think about is how portable the module is. I have a bias towards pure Perl modules - I try to avoid those with C/C++/whatever components where possible. So, a pure Perl implementation may gain favour over a 'wrapper' implementation, since it reduces the dependencies in the code.

But, I think the most important thing is that it has to feel 'right' in the code and fit in with the program - if it causes you to re-write sections of your program, think about why you've chosen it. Maybe it's given you a different view on the problem, and leading you to better ways. On the other hand, maybe it's not.