When should I use a multi-site setup? I have 4 Drupal sites that have nothing to do with each other, except that they all run on Drupal and they're all managed by me. 

The modules each site needs will vary, but they probably share some small subset of modules. 

Is this situation a good candidate for using multi-site configuration? 

What if I want to add a fifth site? How would I upload the new one, or how would that work?
Multi-site setups are a little tricky due to their reliance on the same codebase. You can use a multi-site setup in this scenario, but bear in mind that when you upgrade a module in sites/all/modules, it'll affect all the sites (unless overridden in sites/$SITENAME/modules).

This leads to potential issues where one of your sites relies on N version of a module, but you want to use N+1 on another site. The module in question might not have an upgrade path, or it might've drastically changed its functionality between versions (not as uncommon as you might think, given Drupal culture towards major versions).

Additionally, if there are critical database changes needed during a module upgrade, you'll find that you need to take down multiple sites at the same time to ensure you run update.php.

So for most use-cases, multi-site isn't the way to go. Unless you're really strapped for space or you have some weird hosting restriction that prevents you from mapping each site's domain to a separate folder, you're likely better off maintaining separate code bases and using tools like Drush and version control to speed up code deployment.

The prototypical use-case for multi-site, outside of its use as a workaround for restrictive hosts, is when you're deploying a ton of sites that are extremely similar. You might be running a hosting service, or building a bunch of micro-sites for a company, or what-have-you. In those cases, you can roll your own multi-site setup, but you should also consider using Aegir, which automates and abstracts a lot of the hassles of running such a set-up.

Adding new sites to a multi-site setup is pretty straightforward: create a new folder under sites, edit sites/sites.php (Drupal 7 only), copy sites/default/default.settings.php to settings.php in that new folder, and visit the site in a browser. Drupal should begin the installation process and use the new folder. Your new site will have access to all the modules under sites/all/modules just like your exiting sites.