So does that mean everytime I create a new address on the Bitcoin core, a new Priv+Pub pair is generated?
Yes. (Although with default settings, Bitcoin Core pre-generates 100 addresses)
If yes, how are they all tied to my own wallet? How does the application keep them together for me?
Bitcoin stores all the private keys in a file called wallet.dat.