If u got a gmail acc (most prolly have) and u log in to check ur mails and u dont sign out, then ure signed in to google as well..so when u search, they store ure info..

Best way to avoid EVERYTHING is turn cookies off, turn JS off, if u got chrome, Ctrl+shift+N for anon surfing mode, FF then create new anon profile, if IE, go jump off a cliff.. 

if ure extra paranoid and need to hide ure IP as well (all websites have access to ure IP! ZOMG!) then u can invest some time in finding out a good proxy-tunnelling scheme and surf in peace of mind.