Quickie mockup: bar with search/bookmarks/history options above the results area
To save on menu items and make navigation easy...
I've found the "AwesomeScreen" on the new native builds of Firefox for Android works very nice; it integrates bookmark & history options into the first page of the search screen, so all your "go somewhere" navigations start through the same place.
Attaching a quicky mockup and a screenie of Firefox.
Version: 1.0.0 (Android)