Once you reach level 11 I believe you can do the command 'who sphere'.

Which shows others of the same sphere as you. You can ask them if they perhaps worship the same god..and perhaps they'll help you find the shrine.

ALSO..if you are having a really, really, really hard time finding it. Find an appropriate place to pray...and play it out as your character would. Plead for a sign, whatever you feel your character would do in that situation. And by appropriate place I mean..somewhere meaningful...not The Temple of Galadon.