Finder Tags not working for any SMB files

In a nutshell, how would one access this feature in Finder – not Spotlight (Command+Space) – but the adding of tags themselves?

From Finder, highlight a file and hit Cmd-I (or right click and select Get Info) to bring up the File Info Dialog for the file. In this dialog, the Spotlight Comments field is where you add tag data. Just add text to this field to "tag" the file.

Here's a good article on how to become a meta-data wizard in OS X:
https://gigaom.com/2007/02/01/using-metadata-effectively-in-os-x/

If was tagging that screen capture, I might use the following in the comments box:

customer-name presentation product-name

So that I could find that screen shot by the customer, or by the fact that it's being used in a presentation, or by the name of the product I'm showing them.

Where are these tags stored? Do they go in .DS_Store (I tend to delete those!) or elsewhere in the filesystem?

Yes, they're stored in the .DS_Store files you see in each folder. These files are read by Finder. The information is also stored in Extended Attributes (EAs) on the files themselves. Spotlight will prefer to read the data from EAs. EAs are a feature of the HFS+ filesystem, so remote filesystems might not necessarily have EAs available on files. In these cases, .DS_Store files are the fallback. Spotlight would also have a tag <-> file mapping section in its database but that's only accessible to Spotlight.

Does this tagging mechanism work on removable drives? What are the requirements?

Generally: yes. You can add tags to files and folders on removable drives and remote shares. Unless you've turned off .DS_Store creation on remote shares, OS X will just add these files and keep the meta-data there for you.

Does this tagging mechanism work over a network share? I have some Windows SMB network shares at home that I frequently store files on. Would it work on those or is another configuration required?

Yes, see above. If you didn't want OS X to do this, run:

defaults write com.apple.desktopservices DSDontWriteNetworkStores true

And then restart Finder.

Aside from Spotlight, are there any command-line tools for searching through or accessing the tag data for files?

Lots!

Here's a list of 7 file-tagging applications for OS X: http://mac.appstorm.net/roundups/utilities-roundups/7-file-tagging-applications-for-os-x/

I personally love and use LaunchBar which is like Spotlight on steroids.

Probably the color tags have been disabled previously or some non-color tags are enabled instead. Just open Finder -> Preferences -> Tags and enable all color tags and all non-color tags you need.