I've been looking for a way to tag my files and search/filter them based on those tags.

Here are my (updated) requirements :

• any file readable by the user can be tagged freely
• a user can search for files matching one or several tags
• files can be moved around without losing the previously associated tags
• the system could be backed up easily
• no dependencies on any desktop environment
• if any gui is involved, there must be a cli fallback

I've been hoping for some basic filesystem & coreutils hackery to handle this, but I haven' thought about this hard enough yet.
Meanwhile I'll review beagle and metatracker, which have been mentionned here, and see how they perform.

Ok so beagle has huge gnome dependencies, and tracker is okish, but still has some dependencies I don't like...

Been doing some more research, and the way to go could very well be extended file attributes.
That's a native solution for most recent filesystems, but they aren't very well supported yet (most coreutils destroys them by default, cp for example needs the -a flag to preserve them). Would like to hear some thoughts on using them while I try my hand at some hacks myself, eventhough this might warrant a new question.