It seems to have disappeared. The menu Edit/Search doesn't work, either.
I've filed a launchpad bug-report.
Maybe this answer is just silly, but it is not just the case that the window is not big enough to show the Search textbox? If i resize my window to that size, the Search disappears because there's no space to it be shown.
Gary Lasker from Canoical contacted me through launchpad. He asked me to run Ubuntu Software Center from a terminal using the command line.
I did that and the search box is back. There were no updates in the interim so it possibly was a one time thing (so far).
Thanks to Gary for getting back to me quickly!