How can I change the template based on the category

Is there a way to change the template based on the category I choose in my blog. Whatever theme is unimportant, but how would one go about doing it?

Basically, I want someone to click on the category and then have the sidebar change to give them new choices. Bascially each category will have its own variation of the main theme.

Is this possible? How could I go about it? Is it impossible?