From Wikipedia, before Hanyu Pinyin was introduced, the PRC Chinese learnt Bopomofo or 注音符號 [Zhùyīn fúhào]. It comprises of 37 characters (注音) and four tone marks (符號).
- 注音 consists of consonants, rhymes and medial (e.g. ㄅ,ㄆ,ㄇ,ㄈ)
- 符號 is similar to the four tones in Pinyin except there is no marking for the first tone (ˊ,ˇ,ˋ)
An example: 大 (ㄉㄚˋ, dà) where ㄉ is the consonant for "d" and ㄚ is the rhyme for "a".
There are a variety of ways to look up a word in the dictionary such as 部首查字法 and 数笔画查字法. This article describes the various method.
Update:
As mentioned in the comment by Claw, 反切 (introduced around 220 A.D.) preceded 注音符號, which was introduced in the 1910s. And even before that, there were two other methods, namely 直音法 and 读若法. As the names suggest 直音法 refers to learning by comparison with another character of the same pronunciation while 读若法 refers to learning by comparison with another character of similar pronunciation.
But for all the three methods described above, there is a need to memorise the pronunciation of a few characters first, before one can proceed to learn the pronunciation of other characters based on these characters.