As I mentioned, private mode is broken in safari. There is, however, a workaround:

1. start safari
2. start private mode
3. browse secret websites!
4. exit private mode
5. close all your tabs and the window
6. open a new window (this window will not be in private mode)
7. close the new window

And it works! amazon searches no longer persist! You can now exit safari. This works on osx 10.7.4 build 11E53 with safari 5.1.7.

Alternately… just get chrome. It works out of box.