sudo apt-get install nautilus-open-terminal

This may or may not be needed in Gnome 3.

Anyways, have "search" and "terminal here" available.