Fishermen of the Kerkennah Islands in Tunisia, Moce Islanders in Fiji, and navigation instructors at the United States Naval Academy are the focus of a contemporary study of modern day navigation by the stars. The differences between these communities are obvious, but one of the similarities is the focus of this paper: the stories they tell about navigation. This cultural astronomy project primarily used methods from anthropology, especially ethnography. The stories were collected during interviews in each community from 1998 through 2003. Representative examples of their stories are presented and analyzed. Analysis includes what can be learned and what can be inferred about the navigators, their marine environment, and their relationship to the sky. Though the structure of their stories have parallels, community dependent and reflects different relationships to the sky and to new navigation technologies are emphasised.