If I remember correctly, there was a talk about making people join religion upon creating a character. I think that idea was a good starting point. I think there are few ways to encourage more people to join a religion.
1) Discourage staying as pagan: At the moment, your region becomes unhappy if your ruler believes in something other than what the majority believes in. I'd go one step farther and make peasants despise their lord if the lord stays as a pagan despite the region converting to one of the established religions. Believing in another established religion may irk the peasants a bit but staying as a pagan should be discouraged.
2) Announce holiday or festival: Should boost region's productivity and morale but if the lord's religion and region's religion don't match, it becomes less effective or even worse - something bad might happen due to random religious incidents.
3) When a pagan lord gets appointed/elected to a region, peasants will become unhappy unless the lord joins a religion.
4) Religion in general should be easier to join. I think having a page where you can just select and join one of the established religions would be nice instead of hunting down a temple to do so.
