The answers to the questions you asked are: you can put it anywhere, but best to group with other CSS for the sideboxes and stylesheet_new.
The answer to the question that you haven't asked is: yes you have defaulted to the "Classic"template and yes I would abandon it as quickly as humanly possible. This template is intended primarily for backward compatibility with earlier versions of Zen Cart and has been hacked about somewhat to achieve this making for a rather more complex stylesheet than a new site needs and more tables-based layout than is the case for a completely clean installation based on the template_default.
It would be better to build your own template from scratch based on the functionality in the template_default. A little more work up front, but much, much easier in the long-term.
If that seems a bit overwhelming, an alternative is to start from the Future Zen template which engages template_default for you and amend that. You can download it from the downloads section of this site and there's a link to the relevant downloads page in my signature below.