Note: I use 12.04 so these instructions might not apply to later versions of Ubuntu / gnome-terminal
In gnome-terminal, the system will usually default to using Bash, because that's what gnome-terminal runs.
I overrode that "default" by changing the profile preferences. Open up gnome-terminal (the "Terminal" application), then go to 'Edit' and 'Profile Preferences'.
Make sure you're editing the 'default' profile, and go to the "Title and Command" tab.
Under "Command" there are three checkboxes: "Run command as a login shell", "Update login records when command is launched", and "Run a custom command instead of my shell".
I checked all three boxes, and under "Custom command:" I put zsh.
I also set "When command exits:" to "Exit the terminal" so it closes the terminal window.
Hit the "Close" button, then exit gnome-terminal and then reopen it. It should now start zsh instead of Bash.