The reference librarians at my school are often very helpful. If I tell them my topic, they will help me find many resources which I might not have otherwise found and generally tend to save me a lot of time. Is it common practice to credit them in someway, especially when publishing a paper? If so, what is the common format?
Yes, the acknowledgements section of your paper is an appropriate place to thank anyone who provided valuable assistance. Depending on the circumstances, you could phrase it pretty generally ("I thank the reference librarians at University X for their assistance in conducting a literature search"), you could thank specific people, or you could even identify particular contributions ("I am grateful to Y for bringing the literature on Z to my attention").