The Lync SPLA is licenced on a per month/per user basis. The are 4 SAL types, Standard, Plus, Enterprise and Enterprise Plus (similar to the CALs - Enterprise Plus is equivalent to Enterprise and Plus together). Unlike the CAL model where CALs are additive to give the user extra functionality, only one SAL is required per user.
Update: Basic IM/Presence is enabled by the Standard SAL. The Enterprise SAL gives the basic functionality of the Standard SAL plus the features of the Enterprise CAL. The Plus SAL gives the basic functionality of the Standard SAL and also the features of the Plus CAL, but it does not include the features of the Enterprise CAL. For complete Lync functionality, the user requires the Enterprise Plus SAL.
Lync Server is additional software, so the Service Provider doesn't have to pay or charge for it. The SQL and the Windows OS are chargeable.
Under a SPLA the service provider would normally deploy the solution in their hosting Data Centre, however it can be deployed at the customer premises, so long as the hardware is owned by the Service Provider.