i assume you have the folder for your new theme downloaded... put it at your wordpress directory wp-content\themes , once you do go to your admin panel presentation>theme ... and now its avalable there .. you can select and activate it....
Well, first of all upload your whole theme folder to server ...its better to use smart or core ftp to do so in the wp-content/themes folder. Next go to wordpress account / presentation there you will find the theme u have uploaded...just select it and you are done...
in another way you may go to hxxp://youtube.com and search change wordpress theme. you will see the tutorial step by step on screen.