In the twentyeleven theme each single post page has two navigation links which point to previous and next post, irrespective of the search made by the user. That is, the next post is the successive post in chronological order as it appear in the main blog page even if the user has opened the single post page from a category or tag page, and so such next post could be of another category and tag. Is there any theme/plugin or something else that makes the previous/next post links consistent with the page the user come from?
I cannot think of any one plugin or theme that would handle that exactly; but you could disable the previous/next post links and try rather to display other posts in the sidebar with similar post_types / categories.
This plugin has many options to display easily in a widget area:
WP Category Posts List http://wordpress.org/extend/plugins/wp-category-posts-list/
This is a much more attractive way to get the user to check out other posts that are similar than using the previous / next links.