If you are getting a Virtual Private Server for the very first time or is switching hosts, be sure to ask if Root SSH Direct Access is enabled or disabled upon setup as most hosts will have this disabled for added security.
If SSH Direct Access is disabled on your box, you may need to contact your host to get the option enabled and have SSH Daemon enabled as well.