They want unsolicited SSO with RelayState, and they want RelayState as part of the assertion? (I've only ever seen it as a query parameter).
Well, sent to the SP in the form, typically. Is it possible they're confused? I recent dealt with a vendor who claimed the same thing. I told them it wasn't possible, and that it would be non-conforming. They came back to me that they had talked to their "SAML engineers" and that I was wrong, so I sent them the respective sections from the specifications. At that point, they responded that they didn't really mean in the assertion. They meant in the POSTed form.