I gave a presentation about this at YAPC and OSCON a couple of years ago. You can find my slides here and the sample code here.

In short, I found no important differences in the code you need to write with either one. You might choose one over the other because you like a specific plugin that it has (e.g. Catalyst's session plugin or CGI::App's ValidateRM plugin), or because you like or dislike the syntactic sugar that Catalyst uses. You can also do more with URL mapping in Catalyst without writing code. (You can do all the same mappings with CGI::App, but you'd have to write code to implement some of them. The Catalyst mappings are essentially configuration driven.)

There is also a distinctly different flavor to the communities around them, as you will see if you browse a bit of the mailing list archives for each of them.