The growing adoption of mobile devices and their capability to localize using position technologies (e.g., GPS) has drastically boosted the use of location as a context in online services. These include the popular location-based services, such as door-to-door navigation, as well as online geo-social networks (GSNs). In GSNs, location information sharing is gaining popularity alongside the sharing of other personal content. The variety of GSNs that are available nowadays, ranging from family-locater applications to big social networks such as Twitter and Facebook, point to their usefulness in the daily lives of people. For example, GSNs let people share their whereabouts with others, organize meet-ups, or record their location-enriched activity time-lines. However, the sharing of location information with others, including with GSN providers, entails threats to personal privacy. This is because each location event may disclose highly personal information to privacy-attackers, especially, when it is combined with map-based venue information. Moreover, continuous sharing of location information leads to its aggregation into personal location-histories that compounds the possible privacy threats. For instance, such information can be exploited to identify the people as well as to explain the activities that they indulge in at different locations. To address the location privacy concerns of the users of GSNs, this thesis makes the following five contributions. At first, we present a critical review of existing privacy-preserving mechanisms with regards to the user privacy concerns that they address, and also point out their shortcomings. Secondly, we propose mechanisms that help to automate the manual decision-making process involved in sharing location information in GSNs, by defining location-sharing policies. Such policies are usually based on machine-learning algorithms. Therefore, the training of these policies typically imposes high computational load, which is undesirable on today's mobile devices. In this regard, we exploit mobility information analysis on mobile devices to enable efficient training of location-sharing policies without compromising on the quality of the resulting policies. Thirdly, to highlight the shortcomings of existing location obfuscation mechanisms, we design attack algorithms. These algorithms exploit location-history information that is previously published by the users and, thus, represents an attacker's knowledge about user mobility. This information is used to build mobility models that are subsequently used to prune and de-obfuscate the privacy-sensitive visits of users. Our results show that such attacks are also effective when location-history information is already obfuscated by existing mechanisms. Fourthly, we present a novel privacy mechanism that prevents the aggregation of location history information in the storage infrastructure of GSN providers. By doing so, we protect the user against mobility prediction attacks that may reveal their frequently visited locations, e.g., bars or churches etc., which may represent private habits and personal inclinations of the users. Finally, we also provide approaches that enable efficient sharing of movement trajectories among users while preventing the GSN providers from storing the accurate trajectory information. In this regard, we extend existing privacy mechanisms that protect individual location updates. In particular, we provide novel location update protocols that considerably reduce the communication overhead of incrementally publishing movement trajectories to the storage infrastructure of GSN providers. In general, we evaluate all of our proposed mechanisms in the above described contributions on real-world location datasets.