You're basically wondering how Base58 encoding works. This site gives a good overview but I will list the details here as well with a more concrete example. For this example, I'll just talk about the encoding, but the version byte (prepended) and checksum bytes (appended) do get added before this encoding is done. This prepending/appending just changes the base data before encoding. The below is how the data gets encoded.
Let's say I have this simple encoding called Base4 encoding. In my encoding:
If I have the number 134 (1000 0110 or 0x86) and I want to encode it in Base4, then what I do is repeatedly divide by 4 and use the encoding. Like so:
134 / 4 = 33 remainder 2 -> C
33 / 4 = 8 remainder 1 -> B
8 / 4 = 2 remainder 0 -> A
2 / 4 = 0 remainder 2 -> C
So the Base4 encoding for this byte would be "CABC". Bitcoin does the same thing, but using 58 numbers instead of 4, and a different character for each. The characters chosen in the Base58 encoding are just to avoid confusion when humans transpose the key. For example, there is no I character, because there is already a 1 character, and the two could be confused really easily.
There's just one more thing that's a little tricky. If I were encoding the data 0x0086, I might want the encoding to be slightly different than the above encoding for 0x86 to show that I had an extra 0x00 byte at the beginning. To do this, all you do is add extra data at the left side of the encoding. So, in our Base4, 0x0086 is encoded as ACABC. Similarly 0x0000 0086 is encoded as AAACABC. In standard bitcoin addresses, the version byte prefix is 0x00, and 0x00 is encoded as a 1, so addresses always start with a 1.