I would begin by using HTTP::Recorder to record a successful manual form submission. The output of HTTP::Recorder, just as with WWW::Mechanize::Shell, can be "dropped" right into your WWW::Mechanize scripts. (leira's article "Web Testing with HTTP::Recorder" contains an excellent example of how you might want to do this.)

Note that if you are dealing with javascript, you might need to use Win32::IE::Mechanize. If you run into problems, try Super Searching for "mech javascript" - there are many relevant nodes here.

Another important tool for finding out what is really happening behind the scenes between server and browser is a protocol analyzer such as Ethereal.