You can start with the http://technet.microsoft.com/en-us/library/cc179062.aspx custom outlook profiles. Some reading on that will reveal the keys that they are using, the keys are stored in HKEY Current User (when they are logged in) from what I recall. They bury it pretty well. You might just get away with generating the PRF file and deploy the settings using that.
You are probably searching for your servername or url but you won't find it, it gets encoded a bit in the registry. Most of the values you are trying to change get encoded into hex too, so it's not just a UseProxySetting=1 value. It's more like 1000003009 = 0x229 where 1000003009 is the checkboxes bitmask for all the settings you are looking for rolled into one.
Using the PRF file is the easiest, I've done it via just registry keys before but it can be tricky writing the binary registry values. Also, it's a matter of detecting which of their profiles to add the proxy settings to. Most of your users will have 1 profile which will be the default, but if they have a second one setup from an old migration or something you'll have to play some games with scripting in order to:
1. Find the default profile they are using (there's a key pointing to which one (if any) is default)
2. Update the proxy registry section for that profile they are using.
3a. Cross your fingers that they haven't added their home ISP's email to their outlook.
3b. Make sure your script checks that profile's registry keys to make sure they look like your company's setup (server url is the correct encoded string...) before you make the change...
Hope this points you in the right direction.