The “Add New Themes” link is not available in the Dashboard navigation on WordPress.com-hosted sites because you are not allowed to upload your own themes on WordPress.com. You can pay extra to be able to use custom CSS on WordPress.com, but this is not the same as being able to upload your own theme. There are other limitations with WordPress.com-hosted sites, like the fact that you cannot install Google Analytics and you cannot add plugins.
In general, if you want to start off with WordPress.com-hosted site, I recommend that you pay to register and use your own domain name. That way, if you decide to change your site to a self-hosted WordPress installation, all your links will be preserved.
Here’s what the menus look like in the self-hosted WordPress Dashboard versus WordPress.com: