How to put the main menu and search box on one line?

I have been struggling with a problem for two days now: my "Main menu" block is in the "Header" region and appears in to the right of the site name. I would like to also display the search block in the same region so that it appears next to the menu. However when I add the search block to the "Header" region it appears BELOW the menu, not next to it. I tried finding the right class to modify but nothing I have tried so far worked. Here is what I am trying to achieve:

---------------------------------------------------------------------------
MenuItem1  MenuItem2  MenuItem3                 |               | Search  |
---------------------------------------------------------------------------

I'd appreciate any help on how to style these blocks to get the layout above. Thanks!