Ok, everyone here is the latest.

What Corion suggested did work, ie. I could put my username and password in front of the web proxy such as:
'http://myusername:mypasswd@wwwproxy.mycompany.com:1080'

But I also discovered some verbage at my work about making sure if using scripting and not a web browser to access the internet to make sure the username and password were base64 encoded and not just plug them in as is?

What Thelonius suggested also worked.

Either method seems to work and I guess the only question that remains is in either method is one any more secure than the other and if there is a way to base64 encode within these schemes.

Does anyone know if there is anyway to actually see what headers are getting sent from the perl script?

Thanks for all the help!