It sounds like your clients want to use their own Identity Provider to issue SAML assertions that your SaaS product can use to authenticate them. Hence you would be looking at an Identity Provider initiated logon architecture.
You would need to setup your SaaS product as a Service Provider, exchange metadata and certificates to enable signing, then you can accept SAML assertions and grant the users access. You can use a number of libraries to implement this.
We recently used the open source library OIOSAML to build both an Identity Provider and a Service Provider, both which proved straightforward and reliable. They have .Net and Java versions. Even if you decide to use a different product, both include sample applications and documentation that are very valuble to see SAML in action.