I'm new to concept of TOTP, but as I understand, 16-character base32-encoded shared secret is stored in the client application(for example Authy, FreeOTP)? This means that if I remove the application, the key is lost and I can no longer generate my one-time passwords?
For the Google Authenticator app on Android, the shared secret is simply stored inside a SQLite database file that can only be read by the Google Authenticator app. If you have a rooted Android device, you should be able to view that file and the secret it contains easily.
As for other apps or other platforms, I am unclear about the implementation but I would be surprised to see if it's stored in any other fashion.
It is up to the application really. The exact encoding of the seed is not so important; as long as the application knows how to decode the data and calculate the TOTP on demand.
Depending on the security profile of the service you are authenticating for, it may be quite relevant to consider encryption of the seed. Any OS supplied services are worth considering, but it is not bullet proof.
You should consider if you want to be able to recover the seed, e.g. if the user changes phone or restores a backup; and how you recover the seed. If it is recoverable, it can potentially be exploited to leak the seed.