Custom cache context confusion
How do I get that same invalidation goodness that different routes
  seem to have?


Cache contexts are not invalidated. If you set a cache context, you increase the number of variants cached. For example if you would make a custom cache context for the weekday and set this cache context on a block, you would get 7 variants of the block in the cache. If you don't set any other cache metadata they will remain in the cache and will never be invalidated or updated.


  I notice, in core's core.services.yml, the cache_context.route service
  depends on the current_route_match service, which links to
  CurrentRouteMatch.php and depends on the request_stack service. Which
  of these things is what causes Drupal to end up checking if the route
  has changed? I want to do this same thing for my custom cache context.


Injecting other services in your own service is not enough. You have to use the injected service. 

As example this code from the cache_context.route service you've mentioned: 

public function getContext() {
    return $this-&gt;routeMatch-&gt;getRouteName() . hash('sha256', serialize($this-&gt;routeMatch-&gt;getRawParameters()-&gt;all()));
  }


$this-&gt;routeMatch is the injected service current_route_match. You can see how the service is used to build the context from the route name and the hashed route parameters.


  Will I have to depend on some core service, or is there something I
  can put in either a service definition (in the module's services.yml)
  or the service class itself that says it wants to be updated?


You only have to inject other services, if you need them in your code. But this depends, on what you try to do with your custom cache context.