So, here's an example of what I'm thinking, just to get the full idea out there, I'll have observations of the mechanics in perentheses:
Urist McObservant has known his fellow six founding dwarves all his life. They were all average dwarves from their kingdom. Yet somehow their new fortress is drastically more efficient than anything the other dwarves have ever had (Let's face it, player-run forts are worlds apart from whatever the game makes on its own). Urist McObservant suspects, but does not know, that there's an unseen hand at work here. (At this point you would get an announcement that an unseen hand is suspected. There's no pause involved, it's just there so you know.)
Urist McObservant spends his idle time out in the meeting hall, despite having a room of his own he could settle down in like everyone else. He talks to others, and keeps his ears open for news from the outside world. Looking for some explanation. There isn't one, besides players. After a while, McObservant is convinced. (At this point, you do get a pause. If you were watching closely and checking thoughts you probably already know who it is, but until now you really shouldn't even touch the person.)
Urist McObservant doesn't want to spook whoever's in power until he knows what sort of deity he's dealing with. (At this point you can choose to give him a sign, good or evil, by how you treat him. Elevate him to a coveted noble position, or give him great furniture. Or beat the utter shit out of his life. Assign his wife to stand under a bridge and atom smash her, or send his son outside for a snatcher to take. You could choose to just sit there and not even touch him if you wanted the game to remain the same.)
NOW he knows what you are. He goes to a room all alone, or outside where no one is, and talks directly to you. (You'd get a screen like the Outpost Liason gives you, where he can confront you and ask you what you want from him. Instead of a trade agreement, you'd get a list of possible rules you can lay upon him. In exchange, he'd have prayers you should answer. They're like a Noble's mandates, but the penalty for failure would depend on Urist's personality. It might just be disgust at you as he suffers his way out of your following, or he might just turn into a terrorist and fuck the fortress up before leaving and bringing back an army to kill your fort.)
Eventually, Urist's faith spreads throughout the fortress and everyone is following a standard set of rules that improves fortress life. With the cult flourishing, they begin sending out emissaries to other settlements, spreading the faith. Pilgrims (Probably from multiple races, not just your own) flock to the fortress and it becomes a holy capital. Over time, everyone knows of you in some way. Including the other gods. (At this point we could roll in that pantheon and holy war suggestion that already exists elsewhere in the suggestions forum.)