Welcome to Android Central! Did you only remove the widget or shortcut from the homescreen, or did you somehow uninstall the whole Google App? Did the phone come with the Google App preinstalled? If so, and if the phone is unrooted, you can't uninstall it.