If you have the master private key for an HD wallet, then software can easily generate derivative addresses, and check the balance of those addresses against the UTXO set.
am I supposed to keep generating addresses and check every single one to see if it has any balance?
Wallet software will have a set number of addresses it generates and checks for a balance upon wallet initialization (maybe 50? this will vary and is configurable in some software). The wallet will probably include some logic like "look 50 addresses past the last used address found". You can design this to fit your need, for example if you were a merchant accepting payments on a busy website, you might need a higher bound, in case 50 customers in a row generate a payment address but then don't complete checkout.
Are you supposed to store both the master key and the addresses that you generate to receive payments?
The wallet software will do this for you, but ultimately you do not need to explicitly keep a list of every private key / public address derived from your master key in order to access your funds later. If you have the master private key saved you will be able to recreate all derived keys from it.