Re: my VirtueMart mention. I'd say don't go with that. I don't like the
SEO aspect.
To your question, how does one decide? Based on what you've done with your current store, I'm guessing the following are important to you:
SEO: good keyword url's, lots of human and search relevant content spots and site map generation. I modified VirtueMart to display the product names in the title tag. Creating these title tags was a huge boon to the Google results. See if you can find or hire this feature as it was a powerful move. And Yahoo still reads meta tags so make sure you have control over these.
Products: Unless you are spreadsheet-phobic you'd do well to export your current inventory to a CSV file and upload it to the new store. I don't know your skill level here, you also might either hire someone to do this or input the products by hand. The better the cart's import intelligence the less work/money you need to spend.
For marketing reasons I think you want a mass mailer or an ability to capture customer emails. All you want here is an HTML email tool attached to the store or an ability to dump the store emails to an opt-in list management tool. A built in opt in management tool is better.
Web Design - what's up with the current design? Do you want to keep it? If so you need a template based solution. If you're happy with pre-made templates that don't necessarily promote your brand then any store will have that.
Modifications - does your store do any processing that a typical shopping cart package doesn't have? If you plan to modify the software on a budget go with a PHP-based store. Microsoft/ASP.Net programmers are more expensive (I know, I do both PHP and ASP.Net).
Hosting - {{blatant self-interest warning}} you might want an all in one hosting/ecommerce package, or you might need to make template and behavior modifications to your shopping cart before you go live.... In other words, you might do well to find a programmer to support your initial setup and then do the backups, hosting and maintenance as part of the monthly fee.
Where is the basket/cart on the page - do you have a preference for where the basket is positioned within the user experience? In my opinion it should be on the right side of every page, but there are other opinions (put something in the basket and then show the user the basket). So look at this feature according to how you shop. Maybe you could ask your current customers what they like or dislike about their ecommerce experiences.
User experience -- play with the shopping cart software demos, pretend you're a customer. How do you feel about navigation and information? Are you likely to abandon the cart? If you are so is your customer. Find a cart that works with you, not against you.
Payment, Shipping, Taxes - how comfortable are you setting up the cart's payment options? Can you flip a switch to enter your authorize.net transaction ID? Do you want real time UPS prices? Will you ever have a complicated tax zone problem you'll want to solve? Play with the admin area of the demo carts to get a feel for these solutions.
Wholesale pricing - do you have one price for everyone, or do you need any special features for different customer types?
hth,
Caroline