The best way to move users towards search is to make it crux of your experience, à la Google. Another way is to simply be such a massive and varied retailer that search is the only useful way to get anything done, à la Amazon.
But if neither of these options are acceptable to you, then the question becomes: what do users need to accomplish what your site is there to do for them?
Most e-commerce sites are focused around some particular space of related goods (i.e. a brand), and so it makes sense for users to browse. Browsing can also be an effective way for users to find things similar to but not exactly what they thought they were looking for, but often what they actually are happiest finding. (I've seen this in user research I've done for e-commerce clients.)
To wit: assuming the search functionality is reasonably visible, people will only use it if they think it's the best way to find what they want. So if you want people to use it, you need to make it clear that it's the best way. You might show examples of useful searches, or you could even make your category pages simply execute searches to dump users into that experience as soon as possible.