Set up a Compose key. On Ubuntu, this is easily done in the keyboard preferences, “Layout” tab, “Options” subdialog. Caps Lock is a good choice as it's pretty much useless (all remotely serious editors have a command to make the selection uppercase for the rare times it's needed).
Press Compose followed by two characters (occasionally three) to enter a character you don't have on your keyboard. Usually the resulting character combines the two characters you type, for example Compose ' a enters á and Compose s s enters ß. The degree symbol ° is one of the less memorable combinations, it's on Compose o o.
