How do service tags work? In the user.services.yml, it defines a theme negotiator service as such:

  theme.negotiator.admin_theme:
    class: Drupal\user\Theme\AdminNegotiator
    arguments: ['@current_user', '@config.factory', '@entity.manager', '@router.admin_context']
    tags:
      - { name: theme_negotiator, priority: -40 }


This class determines whether or not the current user sees the admin theme when on the user path.

How does this work? What looks at this and knows when and where to call and instantiate that class? How is it correlated (beyond implementing the interface) to the service below:

  theme.negotiator:
    class: Drupal\Core\Theme\ThemeNegotiator
    arguments: ['@access_check.theme']
    tags:
      - { name: service_collector, tag: theme_negotiator, call: addNegotiator }


Is service_collector something that finds defined services and makes them available by tag name?

What other basic examples of this exist around Drupal 8 core?
Tags are used to find services while building the container by so called compiler passes. They are not available during runtime of the container.

You can find the default compiler passes in CoreServiceProvider::register().

Usually, the tag related compiler passes all do the same thing. Find all services and add them to a service, so that when that service is instantiated, it has a list of service objects that it can do something with.

Thats why this has been abstracted with the service_collector tag, which tells it to pass all services with the tag to the provided method. That's done in TaggedHandlersPass::process()