NEW ANSWER
The easiest way to do it is to install thunar (from the Xubuntu distro --- should be as easy as apt-get install thunar). The Thunar developers have left the emblems option. Once you have set them with thunar, they are visible in nautilus too... so no need to change the default file browser if you do not want.
OLD ANSWER
There is another option, see https://github.com/allefant/Nautilus-Emblems-Menu-Extension/blob/master/nautilus_emblems_menu.py (instruction and plea for help in the same file).
You can drop the file also in .local/share/nautilus-python/extensions directory, no need to go superuser.
Sad, I like emblems. If someone knows how to lobby for that...
(By the way, I tried. I was answered WONTFIX. See https://bugzilla.gnome.org/show_bug.cgi?id=665735 )
You can also add the emblems via command line. To see the emblems a file/dir has associated with it, issue
gvfs-info -a metadata::emblems file_or_dir
To set the emblems cool and default on a file/dir:
gvfs-set-attribute -t stringv file_or_dir metadata::emblems cool default
To clear the emblems on file/dir
gvfs-set-attribute -t unset file_or_dir metadata::emblems
Still looking for a gvfs command to list the available emblems...