I've checked in and out code of starteam before but have never added a completely new project.
What is the exact procedure for uploading a brand new project on eclipse to starteam?
To do this, you need to have special permissions to the StarTeam Repository. Specifically, you need to be able to Create and Modify Projects on the server (these permissions are available in the Server Administration tool, or contact your administrator). Once you have the permissions, it is very simple to create a new Project. Just select Project --> New.
That said, practically speaking, anyone creating a project may also need to have other permissions as well, such as creating and modifying views, setting up users and groups, etc. Therefore, creating a new Project at your company is most likely something that is managed by a special group. Typically, projects may have specific settings or defaults required by your company, may have default folder structures in place, branching structures, project user groups, etc. In addition, if your company is using the Custom Workflow (APE/Alternate Property Editor) for CR Forms or other elements, or other customizations, there may be other steps required in creating a new project.
So although the first paragraph is still technically a correct answer, the more practical answer is probably: contact your StarTeam Administrator.