You could create a new template for each category, as Gothbox suggested, but a more efficient way would to be add a statement to your sidebar that instructs WP to display a different sidebar if the post category=x.
This question was answered in this thread:
http://www.gofuckyourself.com/showthread.php?t=798940