Japanese Language Stack Exchange is a question and answer site for students, teachers, and linguists wanting to discuss the finer points of the Japanese language. It's 100% free, no registration required.
Kanji were originally from Chinese. Japanese used extremely accented Chinese (sorta like what they do with English now) to pronounce Middle Chinese words, which eventually became 音読み. For example 日本 /njit.pon/ became /nippon/. For 訓読み, they simply find the nearest native Japanese word in meaning. You can imagine an English person seeing 走 and pronouncing it "run". Remember that "literacy" in Japan back then basically meant knowing a significant bit of Chinese.
First of all, most people were not literate, and thus had no need of looking up things in dictionaries. Dictionaries back then do give readings in 万葉がな (manyougana), which basically is a finite set of kanji used only for sound. It's like giving the kanji reading entirely in other kanji, used all as phonetic 当て字 (ateji). Example of equivalent in Modern Japanese: よろしくお願いします => 夜炉四句悪袮雅医四魔素