My advice is to go with GTK. Some reasons (in no particular order) are:

• it's simple enough (though probably not as simple as Tk)
• it's written in C (wx and Qt are C++, Tk is Tcl I believe)
• it's cross-platform (though not sure how the new Mac OS X Quartz port is coming along -- you may still have to use X11 on OS X for a while yet if you want to run on OS X)
• it's the standard toolkit for Gnome (as Qt is for KDE and also for future Nokia MeeGo-based smartphones)
• lots of apps use it
• it seems to be the most popular choice among Perlers (though, maybe neck-and-neck with Tk), so you should be able to get enough help from the community if necessary
• the Perl bindings look pretty well-maintained
• GTK GUI's look nice enough (I'm not a proponent of trying to make your GUI look native on every platform)
• good licensing (LGPL)