Even though a part of the decision is your preference, I think wxWidgets (formerly wxWindows) is a very good choice. The Perl bindings are on CPAN (look for Wx), as well as on Sourceforge. wxWidgets is a cross-platform GUI toolkit that can use different engines - Motif, Gtk(2), and the native ones on Win32 and MacOS.

However, not all the classes provided by wxWidgets are implemented (or wrapped, rather) by wxPerl yet. I'm sure help on the development is welcome.

If being cross-platform is not an issue, I would consider the Gtk2 bindings on *nix, probably. It is a relatively nice API and most importantly, it looks good. :)