I'm wanting to create a new controller but when I use the installation provided by my hosting company there isn't a controllers folder

I installed nopcommerce from one of the applications provided by my hosting company. When developing against this there is no controllers folder or a code behind for the global.asax file. Is it possible to create these without messing up the site? I notice that when trying to create a controller from scratch visual studio isn't allowing me to create a controller from a default vs template when accessing the files from the server.

Is there a way to deploy nop to the server with all the folders ect.?

Sounds like you are using the compiled version.  You need to download the source version and you will find what you are looking for.

So, am I able to upload the full version to the server?

Yep.  Search the boards for instructions on how to do this.  There are lots of resources.