When we "deny" consent to tracking on a website, how does the website "know" we've declined?

GDPR legislation pertains primarily to Personally Identifiable Information (PII). Storing dissent in a cookie or localStorage doesn't violate that assuming there isn't anything that identifies the particular user, like trackingConsent=false.

Cookies are not only related to "tracking". They are mostly used to persist the state of the application, like session information or cookie acceptance. It is not gonna work otherwise, only option is to disable them on the browser level, but the legislator chosen to force page owner to do it.

You may provide the page that you are asking about. It quite probably stores your refusal in a cookie or some modern persistent storage. Personally I saw page that after refusal was simply asking again and again.

You may also check by yourself if there are some cookies stored. Depends on the browser, but quite probably f12 button and storage tab.