divide your use cases into two:
a: first x visits (or first visits until the first click on the search box, which means the user now knows it's there)
b. all the rest of the visits after he tried it for the first time
explanation:
a.on the first x visits, or until the user REALIZES that there is a search box - try making it extremely visible. even a blinking animation for a few seconds might do the trick. another nice thing is to animate a text, char-by-char . I have done this on android apps and it even looks sexy to the eye (like those old games) Try to get his attention to the search box at any means possible.
b. once the user actually realized that there is a search box and he actually tried to use it - he is now educated. he knows there's a search box. In this case, you can minimalize your search box to a tiny search button. remember - the user already knows it's there. if he needs it - he'll know where to find it
Any feedback/criticism will is welcome.
(edit: spacing)