He is a random encounter, and can be found wandering in the wilderness. The Dragonborn has the option of traveling with him to the shrine, or Faldrus can tell the exact location of the shrine to Dragonborn and marks it on their map. He can lead the Dragonborn to the Shrine, possibly starting the Daedric Quest "The Black Star".
If Faldrus is killed, he may be found in a second random encounter, so killing him is of no consequence. Even if Faldrus does not show up in a second random encounter, he may show up at the Shrine of Azura.