The actual way this should be implemented, if they wanted to be morally irreproachable, would be this: a consent popup always available, tucked down somewhere in the corner of the site. It defaults to opt-out from everything, you can click on it to expand it if you want to opt into something.
An acceptable option is to pop up a consent form as needed, and set a cookie recording whether user made a consent decision. That can be classified as essential cookie to fulfill a legal obligation.