The Ubuntu Software Center normally has a search box in the upper right corner. However, if the window is sized slightly smaller than usual, that search box goes away. This is an error in how the responsive design of the interface was setup.
You can see examples below. The top example is of the window when it’s not sized large enough. The bottom example shows a slightly wider view. Click either image for a larger view.
A better method would be to resize the icons or have a ‘more’ indicator button to expand out and see other options.