Aditya,
You've found a great CMS to work with, and a great community to support it - great choice!
As Spike mentioned, Arvixe is a great hosting provider; setting up a staging environment is as easy as creating a subdomain, setting up a database through your hosting UI, and installing your "testing" installation on the subdomain (ex: mytestingsite.myexistingdomain.com). This is my standard procedure for my clients, to allow better pre-launch collaboration.
Since you can point to the same database from either the primary or subdomain, it makes it easy to get everything set up, then when the staging site is fully prepared, approved, and ready to go, install mojo to your primary URL (www.myexistingdomain.com), and instead of running the install, just point the connection string to your existing database, and your new instance is live, and ready to rock.
One caveat; make sure that any images you use in the staging server site are copied over to the live site before you make the switch, to avoid "broken" image links.
One of the ways you can ensure that existing site traffic won't hit a "page not found" error is to utilize the 301 Redirect feature in the Administration section of mojoPortal. You can point old page URLs to their new counterpart there, and your site visitors will barely notice a thing.