Open gconf-editor
Go to desktop => gnome => terminal
Set "exec" to "gnome-terminal --geometry ??x??", where ??x?? is the default size you want.
Update: In Ubuntu 12.04, you can set gnome-terminal's default size in "profile preference => general" without hacking gconf-editor.
