Turns out that this wasn't a matter of cookies or headers (I tried adding both to the request with no results). The functionality for sending the request was perfectly fine--it just turns out that trying to send the XML formatted as Utf-8 was messing things up.
When I removed that from the XML, everything went through just fine, and the server spit out the right data.