With the proliferation of mobile devices such as smartphones and tablets, location-based services are becoming increasingly popular. LBSs, albeit useful and convenient, pose a serious threat to users' privacy as they are enticed to reveal their locations to LBS providers via their queries for location-based information. How to protect users' privacy against potentially compromised LBS providers is of vital importance to the well being of the LBS ecosystem, given that the LBS market can expand and prosper only if users feel comfortable about using LBSs. This article presents a comprehensive overview of the existing schemes for protecting LBS users' privacy. We first introduce potential privacy threats to LBS users, followed by a discussion on privacy metrics. We then classify the protection schemes according to their architectural properties (i.e., server-based or mobile-device-based) and privacy metrics (e.g., k-anonymity or location entropy). Finally, we discuss several promising directions for future research into LBS users privacy protection.