> … how do you prove the citizen has agreed to you storing their information?

By having participated in an actual business transaction, which usually leaves an (electronic) paper trail.

Take note that simply visiting a website can not be interpreted as a business transaction. If anything this is accounted for as browsing the displays of a street vendor.