Integration of a tag based file system approach in Gnome and Nautilus

I've found tmsu to be the best, it can be found here:

http://tmsu.org/

It doesn't integrate into Nautilus as such but as it uses a FUSE filesystem, it can be browsed from any file manager or even on the commandline.

As far as I know, there is a nice file system level solution to your need called NHFS or nonhierarchical file system. Also available a FUSE based mountable file system called TMSU that may satisfy you. Since these tow are solving your problem in a file system level, they are fully compatible to Gnome and Nautilus.

Also if you are looking for a program such as a collection manager, and not a file system; best open source working solution in Ubuntu I can introduce is tagspaces. It seats independently besides nautilus, no integration at the moment.