Car sharing holds a promise of reducing traffic congestion and pollution in cities as well as of boosting the use of public transport when used as a last-mile solution in a multimodal transportation scenario. Despite this huge potential, several problems related to the deployment and operations of car sharing systems have yet to be fully addressed. In this work, we focus on station-based car sharing and we define an optimization problem for the deployment of its stations. The goal of this problem is to find the minimum cost deployment (in terms of number of stations and their capacity) that can guarantee a pre-defined level of service to the customers (in terms of probability of finding an available car/parking space). This problem combines insights from queueing theory (used to model the stochastic demand for cars/parking spaces at the stations) with a variant of the classical set covering problem. For its evaluation, we use a trace of more than 100,000 pickup and drop-off events at a free-floating car sharing service in The Netherlands, which are used to model the input demand of the car sharing system. Our results show that the proposed solution is able to strike the right balance between cost minimisation and quality of service, outperforming three alternative schemes used as benchmarks.