To get it back, you can scroll up, of course, but that's time consuming. Instead, just tap the status bar (carrier, wireless strength, etc.), as you can do in Safari to jump to the top of a web page. This will take you to the top of your Contacts, bringing the search field back into view.
I can't remember where I heard this one, though I think it was from a fellow Macworld writer during an iPhone 2.0 software conference call. Best as I can tell, though, it's not documented in the latest version of the iPhone user's manual (which is some 22 pages longer than the January 2008 version).

