Cookies are specifically a website thing, but apps will store similar data for similar uses.
A server won't necessarily send old data to your new phone. It'll send a "token" to your phone, then afterwards every time the app communicates with the server, it'll send that token along with the data for authentication.
The app/service will likely try to get identifying data from the phone to track usage even if the app is uninstalled (deleting the app data) then reinstalled. The app/service can also theoretically link two accounts if they determine you're using the same phone for a new account.
You can read more about what kinds of identifiers apps can get from your phone on the website here under both hardware and non-hardware identifiers. But a tl;dr version would be apps cannot really get unique identifiers. There's one identifier that will reoccur if you reinstall an app, so to avoid that you can use a new profile. A new profile won't have any unique identifiers an app/service can use to id you, however they can attempt to guess based on other things like IP address, carrier, etc.