You need to make this check before the general controllers are called. I would suggest an approach like this:
1) Listen to the init_dependencies code event or something else that probably better suits your needs. According to description, "This event is fired on virtually every page and is the first thing you can plug into.". This listener is where your "gateway" is placed. It will check if the user has agreed to your terms.
2) I think a database table would be the best choice to keep record of the user's agreements. A record is created on this table only when an user agrees to the terms.
3) I would create a controller where I explain the terms and include an appropriate call-to-action button. Obviously, the listener created in the first step would let the user pass if he enters this controller.