Where are shell/terminal settings stored?

GNOME Terminal profiles are stored in: ~/.gconf/apps/gnome-terminal/profiles.

(You might want to back up the whole .gconf directory, though.)

Newer gnome-terminal (3.8+ I think) stores its config in dconf instead gconf.

gsettings list-recursively | grep -i org.gnome.Terminal

More info about the change https://askubuntu.com/a/91409/79266