Luke,
Here at WordPress.com it's not possible to upload your own themes, you need to choose from the pre-loaded themes (you can also customise them with the Custom CSS upgrade), so this is why you're a "Install Themes" tab under Appearance > Themes in your dashboard.
Don't worry though - there's an awful lot of flexibility here at WordPress.com, both through the aforementioned Custom CSS Upgrade which allows you (if you're CSS handy) to customise one of the existing themes to your needs, or perhaps by looking at one of our Premium themes.
If you're having trouble finding a theme to suit you, you can browse through the Theme Showcase.
To clarify, uploading themes is a feature of self-hosted, WordPress.org powered blogs, not those here at WordPress.com so tutorials you're seeing referencing installing or uploading themes are geared towards WordPress.org users. There's some extra documentation which outlines the differences between the two here.