For further clarification, you need to visit a temple of a player-created religion. They are listed as: "Visit the 'Sanguis Astroism' temple", or whatever the religion is named. Inside it, there should be an option to apply for membership.
The action of " Visit the temples... - chat with the local priests." is a holdover from back when there were no official religions. It let's you get a little information about the region, but you cannot join it.