But I am not even sure if this is correct. And the details eludes me. For example: How do I discover what name to include in myservice.services.yml?

Now that Drupal 9 is end of life you no longer need to do that. Replace the argument list with the autowire option:

mymodule.services.yml

services:
  mymodule.my_service:
    class: Drupal\mymodule\MyService
    autowire: true

See the change record: Core services provide aliases for autowiring

But I am not even sure if this is correct. And the details eludes me. For example: How do I discover what name to include in myservice.services.yml?

Now that Drupal 9 is end of life you no longer need to do that. Replace the argument list with the autowire option:

mymodule.services.yml

services:
  mymodule.my_service:
    class: Drupal\mymodule\MyService
    autowire: true

and in the service class:

  /**
   * The date formatter.
   *
   * @var \Drupal\Core\Datetime\DateFormatterInterface
   */
  protected $dateFormatter;

  /**
   * Constructs \Drupal\mymodule\MyService
   *
   * @param \Drupal\Core\Datetime\DateFormatterInterface $date_formatter
   *   The date formatter.
   */
  public function __construct(DateFormatterInterface $date_formatter) {
    $this->dateFormatter = $date_formatter;
  }

So to discover the service you only need the interface DateFormatterInterface. Use autocomplete and the IDE will automatically add a use statement at the top:

use Drupal\Core\Datetime\DateFormatterInterface;

See the change record: Core services provide aliases for autowiring