Choose sidebar menu based on viewed page

I want to choose the sidebar menu based on which page I am looking at.

I am currently using the twentyeleven theme.

On one set of pages, I want the sidebar to have a custom menu title, and a certain set of links. On another set of pages, a different menu title and different links.

Any thoughts on how to achieve that? I’d really rather not embed that in the page itself.

I was thinking that I could create a separate template for each group of pages, but then I also need to somehow create a new menu for that template.

I am pretty sure at the moment that this will require some custom programming; if you have a better idea, I’d love to hear it!

Thanks