Is it possible to use a font not listed in my theme appearance page for the menu and side bar with the CSS upgrade and if so could you help me out with how to make this happen?

Sure! Check out this page about font stacks first:
http://unitinteractive.com/blog/2008/06/26/better-css-font-stacks/

Here is an example showing how to change the fonts for the menu and sidebar in the Forever theme:

#access a,
#secondary .widget-title,
#secondary {
	font-family: Georgia, Palatino,” Palatino Linotype”, Times, “Times New Roman”, serif;
}

Note that it's possible text for some things you add may have more specific selectors. If you find an example, you just need to examine it in the page's source view in your browser, determine the selector, and add that selector to the example above.

The answer is yes but it’s important to know that regardless which fonts you may wish to choose to jazz up your blog with, your browser and your visitors’ browsers can only use the fonts installed in the same computer. If a reader does not have a specific font installed on his / her computer, the browser will determine which font is displayed.

Just to clarify, the above is only true if you use a font stack via CSS—the Custom Fonts are loaded (and licensed properly) via the web and each reader's computer doesn't need to have the font installed in order for it to show up.

(Just posting this to make sure people coming back to read this later don't get confused about the differences.)

The answer is yes but it’s important to know that regardless which fonts you may wish to choose to jazz up your blog with, your browser and your visitors’ browsers can only use the fonts installed in the same computer. If a reader does not have a specific font installed on his / her computer, the browser will determine which font is displayed. There are a very limited number of fonts (in English/Western languages) which are common for most operating systems/computers/browsers.