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.