A rime-book (Chinese yun4-shu1) is a traditional Chinese dictionary in which characters are arranged by pronunciation. The most famous and important of all the ancient rime-books is the Qieyun, dated 601 C.E., and its two main redactions, the Song dynasty Guangyun and Jiyun. The Qieyun had some 12,000 characters, and its successors roughly doubled and quadrupled that number.
Characters in rime-books are usually arranged by rime, meaning the rhyning (end) part of the Chinese syllable. The books in the Qieyun tradition are divided up by tone-category, with the entries for each tone-category subdivided by rime, and each rime further subdivided by homophone group (in Chinese, xiao3-yun4, "small rime"). So each character that you find will be placed in a small xiao3-yun4 section with its exact homophones, and in a larger yun4 "rime" section with words that rhyme with it exactly.
Pronunciation in the rime-books was indicated by means of fanqie "spellings".
Rime-books must have been hard to use in traditional times, because there were no indexes until about the 1920's. I suspect their most practical use was in the composition of poetry. Since Chinese poetry necessarily rhymes, and since that rhyming was the subject of a set of rules for use in official examinations, we can be sure there was a developed consciousness about what rhymed with what in medieval China. As long as you can find the right part of the book for the rime category you want to use, you can probably find the character you want. But if you are trying to find out all the pronunciations of a given character, you have no choice but to make educated guesses about where they might be, or else skim through the whole book.
Some of the rime-books are repositories of much traditional lore, and you can learn a lot by reading them, although I think very few people now do that.