The main page for P3P is
P3P: The Platform for Privacy Preferences. The links there will cover pretty much everything you need to know. If you look at the cookies that Google uses for Google Analytics, in the header from Google you will see a line starting with P3P: followed by a series of three letter abbreviations. Adding this to your server's headers may allow customer browsers to accept third party cookies.
Basically, by default, IE blocks all third party cookies that do not have a privacy policy, or that have a privacy policy that is outside certain limits (ie, sells the collected data). If you implement a P3P policy that is within the default boundaries, the cookie will be accepted. However, the policy has to be implemented by the company setting the third party cookie, rather than being set on your end.
After looking at the headers being sent in IE, where you indicated the problem is occurring, the referrer is being sent correctly. The problem is in the cookie not being set. The other option would be for the other company to develop a system that does not use cookies.