It is definitely easier if you have the perl source available. It has been a long time since I have done this, but you should be able to compile it all with -g (and -DDEBUGGING) to enable the debugging stuff, and do

gdb /my/debugging/perl 
(gdb) run my_script my_args
[download]

To make your life even easier, while you are recompiling your perl, link your .xs module in statically -- it will make setting breakpoints and the like easier, because your module will be loaded in from the get-go.
Another little trick is to use the perl debugger too:

gdb /my/debugging/perl
(gdb) run -d my_script my_args
[download]

Hitting Ctl-C from the perl debugging prompt will (or at least should...) drop you back down into the gdb prompt. (click here for a post showing an example of this trick in use...)

It should also work with dbx or any other C-level debugger.

Best of luck...

--JAS