People-Nearby applications are becoming a popular way for individuals to search for new social relations in their physical vicinity. This paper presents the results of a qualitative study, based on 25 interviews, examining how privacy and locality are managed in these applications. We describe how location is used as a grounding mechanism, providing a platform for honest and truthful signals in the challenging process of forming new social relations. We discuss our findings by suggesting theoretical frameworks that can be used to analyze the social space induced by the applications, as well as to inform the design of new technologies that foster the creation of new social ties.