Check out https://fidoalliance.org/specs/u2f-specs-master/fido-u2f-overview.html for details on how this whole process works.
U2F is built in a rather flexible way, so there's also the possibility for the token to have onboard storage and keep its private keys to itself, however it doesn't have "unlimited" storage anymore in that case.
Another nice feature of FIDO U2F is that credentials are bound to an origin, in order to prevent phishing.
A website can't simply say to your token "please sign the login for user ID XY". Instead, the browser will also include the origin (host name & port) to that request, allowing the token to check whether the requested keypair is indeed associated to that origin.
In case the website stores the encrypted private key, it also stores this information (decryptable by the registered token only).