Hi Steve -- this looks like an amazing project -- I hope one day to see it with my own eyes -- with regard to the links to interesting sites and videos, I have to say that I love the christmas tree one -- wow!
Jack focuses on software, but there are other techniques. A pullup resistor with a capacitor works well (preferably followed by a schmitt trigger) for slow responses although you should be aware that when you close the switch a short spike of high current will flow through the switch. You can limit that with a small series resistor. A cross coupled NAND or NOR gate combination will work if you have a changeover switch. Also if you use a non-inverting buffer (like 2 x 74HC04 in series or a MC14050) and connect the output to the input by a 10K resistor and also use a changeover switch you will have a debounced output.
Other manufacturers also make debounce chips. Maxom does the MAX812 and several others. See this app note.
At the outset this eeems like a simple thing to do, but take care. Changes in approach often may mean rewriting your driver from scratch. After working with a customer who chagend their mind frequently I created an approach to allow a systematic method to create hierarchical menus and how to display dynamic data within that.
I wrote it up in a Circuit Cellar article "hierarchical menus in embedded systems" published in issue #160, November 2003. Circuit Cellar's business model requires you to pay a small amount, and for articles of that age you have to download the whole magazine. Let just say that the code was written for the Rabbit micro, but is all in C and should be easily portable.
It sounds like you are going through quite a steep learning curve.
But the project and what you are producing look worth the effort.
Rotary encoders can be a pig to debounce, I usually do this in software, its almost a trade against filtering the input and missing clicks on the swich position, which can be annoying, especially with counting up and down.
I have not tried it yet but, I think a timer reset after each interrupt from each bounce and read the state of input pins when the timer is able to time out. This should take out the problem of switches getting worse on bounce as they get older.
As it is an Atmel chip are you using Pin Change interrupts?
Max can give you my contact info in England, if you want to discuss Atmel chips and software offline.
@Crusty @Steve: As it is an Atmel chip are you using Pin Change interrupts?
Thinking about it, there are de-bounce functions in the Arduino library. Steve, do you have the Arduino Cookbook or the Arduino Workshop? (Both are recommended, but if you only get one, make it the Workshop). They cover this sort of thing.