Here's what I'm doing:
I tag a video in Photo Gallery. It appears under that tag along with any other videos or photos with it.
However, when I go to Media Center, there is no option to sort videos by tag. If the tag contains both videos and photos, Media Center "sees" the tag when I go to the photo section, but does not show the videos that have been given that tag under Photo Gallery. Media Player, as far as I can tell, doesn't have tagging capabilities (and doing a Properties view of a video doesn't list its tag).