Had this problem with linux mint 17. The default key theme seems to be Emacs there, but almost no other tool than gedit care about that (which makes it look like a gedit problem, but it isn't. It's just that linux has become a config spaghetti).
The solution is twofold:
the key gtk-key-theme has to be changed from "Emacs" to "Default" in both GConf (the old config system of gnome) and DConf (the new one). You can access GConf via gconf-editor and DConf via the linux mint settings dialogs, or directly via gsettings.
Open Linux Mint's System Settings -> Themes -> Other Settings. Here, switch the drop-down menu Keybindings to Default, and close the settings dialog. Don't ask me why this setting is in "Themes", and not "Keyboard". Brain fart.
This should have done it for gedit. Alternative route is using the command gsettings set org.cinnamon.desktop.interface gtk-key-theme Default
However, The gnome developers who made DConf aren't smart enough to synchronize backward compatible settings with GConf. So open gconf-editor (and this is what the gnome-tweak-tool mentioned in Tingting's answer also accesses) and navigate to desktop->gnome->interface. There you'll also find the key gtk_key_theme, which you now also set to "Default".
That should be it. What a beautiful example of miserable design and defaults (Emacs-keys as default system wide? seriously? Because Emacs users are so bad at changing configs to their needs?)
Adding some keywords for google: gedit CTRL+F control F doesn't search find work moves cursor forward CTRL+H control H doesn't replace work deletes character