I have opened up a small temple inside our Newbie School. You may ask the man standing before my temple about worship and he will explain the process to you. Once completed, he will also offer you the chance to list the different types of Holy Items which we offer.
These options are also available on the only other temple on Newbatia.
Enjoy,
Splork