A few hours ago, Google announced that you can now sync your mobile and desktop Google search history.Available for Android, iPhone and Palm Web OS, all users need to do is log-in to their Google account. From there it's a matter of enabling or disabling from the settings tab.
More information can be found at the Google Mobile blog here.