I haven't used Android with GApps for at least a year or so, so I don't remember exactly how it behaves. But there should be a Google search bar on the home screen, see this screenshot I found:
IIRC it's not a widget, so it doesn't take any space in the grid you got for icons and widgets. Furthermore, it's visible on all home screen pages.
I believe the setting I have is simply for changing that search bar's search engine provider. I don't think CyanogenMod have done that many changes to Android, so I would guess that the setting is available in regular Android as well, but please correct me if I'm wrong.