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.
So it generates 100 priv+pub key pairs at the time of installation but does not show them up. Once I click on generating new addresses, it picks one of those and show it to me? If I go beyond 100, it generates new priv+pub key everytime?