I’ve not seen a site that remembers your selection of “reject all”/“essential only”. It would actually be hard to argue that it would count as an essential cookie, nothing about the site depends on remembering your rejection. I guess that makes “maybe later” more reasonable since it’s going to ask you every time until you relent.
Huh? Of course those get remembered, and of course it's allowed by GDPR. If the websites you visit don't remember "reject all", they're doing it maliciously (or out of incompetence, I guess).
"Reject all" doesn't have to be cookie, the answer could go to the browser storage.
Basically it just exists in your browser, telling it "the user didn't agree to cookies, so don't send this data and don't render those blocks". The only thing that web server knows is that requests come from someone who didn't send any cookies.
I believe it's a very common implementation.