At present, the free version of WP e-Commerce does not come with a product search feature. The ability to grant customers a way to search for specific products on your site is, unfortunately, one of the most-pressing reasons to upgrade to the Gold Cart. Every competing plugin to WP e-Commerce allows for product searching by default, even in their respective free versions, so it is unfortunate that the WP e-Commerce developers feel the need to relegate this necessary feature to the paid version (although they have every right to do so). Shop owners with large product catalogs will especially feel the need to upgrade to the Gold Cart as a result.
On the other hand, the Product Search feature that is unlocked when you buy the Gold Cart is very well done. It is more than a simple search box. It also offers some advanced searching capabilities as well as a slick Live search options, which automatically starts suggesting results as the customer types instead of waiting until the Enter key is pressed.
To enable Product Search, navigate to the Presentation tab under your WP e-Commerce settings. About halfway down the page, you will find a Show Search option:
When Search is enabled, you will now find an Apple-esque search box on all of your store pages:
Note
Keep in mind that the WP e-Commerce Product Search feature only works for the products in your store. It does not also search your regular WordPress posts and pages. There is a third-party commercial plugin available to unify Product Search and WordPress search: http://embeddeddreams.com/users/njay/suniwpsc.php