Where do the files of a custom WP CLI Command reside?

You can put the PHP anywhere in your plugin, or a file that’s included into your plugin, the same as you would any other code for extending any part of WordPress in a plugin. The only thing you need to do is check that WP_CLI exists before using any of the WP CLI API:

if ( defined( 'WP_CLI' ) && WP_CLI ) {
    // WP_CLI::add_command etc.
}