What are the different ways to encode a Bitcoin Address (both private and public) and how are they calculated? I've heard of things like firstbits, mini private key format, and I`d like to know how does one convert one number into another.
What you're talking about is actually two separate concepts. A "Bitcoin Address" is not a keypair, it does not have public and private components. The Address is derived from the public portion of the key pair and is almost always expressed as a Base58 string.
Firstbits is merely a way to look up addresses. When you enter someone's "firstbits" address at firstbits.com, firstbits converts what you've entered to all lowercase characters and then looks through the block chain to find the first (chronological) occurrence of an address beginning with that string. You can't send coins to my firstbits address of "1enmaku" for example, but plugging that into the search box will produce an address "1EnmakuaAN1WgAK2tUFvmsYcKc3NvH3NML" which is valid.
The others mentioned are all methods of expressing the private key. An address represents a receiving address, but the private key represents the right to claim coins at that address. A private key is a 256-bit number which can be represented in many ways. The most common way is WIF or "wallet import format" which is a 51-character string in Base58 which always begins with the number 5 and has some built-in error checking.
The mini private key format is also seeing some widespread use such as in Casascius' physical bitcoins. Mini private key uses as few as 22 characters of the same Base58 encoding as Bitcoin standard addresses. There are some criticisms that the fewer number of characters represents a smaller number of bits, making these keys vulnerable to brute force attack, but even the smallest of them still represent a substantial amount of entropy.