Set your title to something reflecting both the seeker and the youngster properties of your character. The latter is to make sure you mitigate any accidental ganks by your future enemies.
Post in-game on the religion board. I am determined to bring that into style!
Do a who and ask anyone who looks like they're movers and shakers in the religious scene... even if you don't find your target faith, ask anyone with obvious religious titles you think might be amiable. They tend to know Who's Who even among other faiths.
Last but not least, do what you can to make your interactions with others as fun as possible. Nothing kills a good conversation fast than starting a seeker conversation with "LFG." I've had a few already.
... These are just some of the tips that worked for me.
