If you're talking about IAnonymousIdFeature, then it is generated in AnonymousIdMiddleware, used in middleware pipeline with app.UseAnonymousId().
The ID is generated in the middleware with Guid.NewGuid() and stored in "EPiServer_Commerce_AnonymousId" cookie, and to my understanding it's not stored in database (with default implementation).

No, it is not stored separately in the database. And the middleware that generates the Anonymous ID has no event to hook into. The only where it is stored, is the shopping cart.

But I was thinking, if you don't want to pass the anonynous id cookie (many native apps prefer not to), and instead wants to include the anonymous id in the token, then you could look into generating your own as part of the token process.

Then you could add your own middleware to unwrap the token and get the anonymous id claim. As long as it adds an implementation of IAnonymousIdFeature before the built-in middleware, then the built-in will not run.