Typically you would set up the store on your local machine, modify any files you need to (templates, css, any additional plug ins, etc). When you are done, you would do the same base installation on your remote host and then overwrite the files on the server with the files on your localhost. Make sure to keep track of any configuration files that have information that is specific to the server. These will typically contain the username password and host for your database, and perhaps some path or domain info. You will need to change these to the values of your remote host.
Don't spend a lot of time on your localhost setting up categories and entering products. If you do, then you will also have to do an export of your database and then import the values, which is not a big deal if you are familiar with that, but if you're not, it could cause headaches. I like to use a mysql gui to handle the database stuff, it is easier than doing it thru the console.
If you are using osCommerce, you may want to look at CRE Loaded. It is based off of osCommerce, but is supposed to be a little bit nicer, I've heard. I will be needing to set up a store with it in a couple of weeks for work.
