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.
It is possible using cookies.
Cookies are nothing but small pieces of data (name-value pairs) that is stored in your browser by the web application you are communicating with. Every cookie has a domain associated with it and a cookie belonging to example.com can not be accessed by abc.com. It is important to note that whenever browser makes an HTTP request to a certain domain all the cookies associated with that domain are also sent along with the request to the server.
In SAML terminology
Identity Provider (IdP) - Provides authentication as a service
Service Provider (SP) - Relies on IdP for authentication of its users
SSO using SAML : let us say there are two services SP1 and SP2 the user wishes to access.
User visits SP1 and tries to log in. SP1 sends an authentication request to IdP and the user's browser is redirected to IdP where he enters his credentials. After successful authentication the user is again redirected to SP1 and IdP sends an assertion to SP1 which contains authentication information. Now the user is authenticated and may use the services of SP1. In this case the response coming from IdP also contains a cookie to identify the user. This cookie is stored in the browser.
Now the user opens another tab in the browser and tries to access SP2's website. Again as he tries to log in the browser is redirected to IdP and with this redirect the cookies set by the IdP are also sent. The IdP receives the cookie and sends an assertion redirecting the browser back to SP2. The user is logged in to SP2 without needing to enter his credentials again.