"It is by interrogating the Cookie that the browser finds out 'what to do', if that is not an instruction, I would love to hear your definition of what is."
Software is described as a series of instructions, yes, but they are programed instructions compiled into code that a computer can execute. Those instructions can include the reading and processing of data, and that data can be used in decision making within the software, which can then affect the software's behavior.
A Cookie is, by definition, data. It is not software as it can not be executed by a computer. Instead, software can read a Cookie and take the content to determine how the software is to behave.
Or look at it another way: I go to a website for the first time: The website can't find a cookie, but it is still able to function properly. If I delete the cookie it creates, it will still work: It will just loose the setting, preferences and other data it was storing on my PC.
So rather than referring to Cookies as instructions, it would be safer, and perhaps more accurate, to refer to them as preferences and/or settings.