WOW! What a nitemare you have there, well it depends on the software you use for the new shopping cart.
You will want to do 301 redirects for every page. Do you by chance have a csv file with all your products and the corresponding url's? If so, this would be the easiest, rather than going through manually putting in each redirect.
Also, if you are moving to a shopping cart that has SEO friendly url's, this will help you even more with your positioning, and could quite possibly give you a really large boost in organic traffic.