Update: I just learned that there is indeed a way to tag files in Linux (well, in KDE apps at least). In its current incarnation it is called Baloo, and it is now implemented pretty much like tags are implemented in OS X, that is by incorporating the tags in an extended attribute for the file.
Unfortunately when I google "baloo kde" I do see quite a bit of pages asking or showing how to disable Baloo. I guess it's still in its infancy and still suffers from performance issues. (Baloo actually does much more than tagging, it is the whole file indexing system, so it is more akin to Spotlight on the Mac side.)