I don't think anything is actually "necessary" if you want to be strict on definitions.

I think it's absolutely fair and unlikely to be illegal to use a cookie to remember cookie preferences. Unless the cookie value was not yes/no, but something like a precise timestamp that could be used for uniquely identifying.

Yes, it is strictly necessary to properly honour the user's choice. Not storing a rejection of consent but storing acceptance violates the GDPR because it creates an asymmetry between the effort required to accept vs the effort required to reject user data processing.