in reply to Ok I'm stumped. How the heck does LWP::Authen::Wsse work?

I think this is where I'm going wrong. Is the server supposed to send a special header asking for WSSE authentication like it does for Basic Auth?

Yes

Or does LWP::Auth::Wsse (which only has one method called authenticate) have to be injected into a WWW::Mechanize object somehow?

No, it only has to live in the LWP::Authen:: namespace, be named ucfirst lc $authenschemename, and have a method called authenticate :) LWP::Authen::Wsse qualifies

but I can't seem to get from A to B. Help!

Its all about the headers sent and headers received, examine the headers, or show the headers :)