How is SAML solving the cross domain single sign-on problem?
It actually can be a cookie, because it needn't be associated with the service provider at all, only the identity provider. All either of the two service providers are going to do is make the authentication request to the identity provider, so the process for an unauthenticated user is going to be the same for sp.example1.com as it is for sp.example2.com.
However, when the first request is made from sp.example1.com and the user is redirected to sso.example3.com, the user will login to sso.example3.com and can then set a cookie for sso.example3.com.
Then, when the user visits sp.example2.com, it too will redirect the unauthenticated user to sso.example3.com, but this time, the browser will have a cookie to send along with the request from the last time the user visited sso.example3.com, even though that visit was initiated by a different service provider.
Thus, the cookie from sso.example3.com can identify the user as already authenticated, and the identity provider can continue the process of issuing an assertion for the user to sp.example2.com without requiring the user to complete the login workflow again.