Implementing Custom Cache Tags I would like to use the new Cache Tagging in D8 to help keep related content of different types (entities, nodes, blocks, etc) in sync. But from reading the currently available documentation of this feature I do not understand how to add my own cache tag to the items of content when creating/updating said items.

For example when creating a new node of an type Store I would like to add the cache tag location:new_york_123 and the same for a a block. Then if I changed the display name of the New York 123 location to SoHo, I could invalidate the cache tag and have all related content update.
Here is how to use cache tags in the context of custom blocks which I have tried and works but I think it applies to other contexts
Use default drupal tags
In the build array you can specify cache &gt; tags &gt; node_list and this block content would get invalidated (refreshed) when ANY NODE is  changed with nothing else to do on your part
public function build() {
    return array(
        '#markup' =&gt; MY_MODULE_awesome_dynamic_node_content(),
        '#cache' =&gt; [
            'tags' =&gt; ['node_list'], //invalidate when any node updates
            //'tags' =&gt; ['node:1','term:2'], //invalidate when node 1 or term 2 updates
        ],
    );
}

Alternatively you can put in one or more node/term/user IDs to invalidate the array on specific nodes or terms as shown in the code comment above.  Note: you can mix and match nodes, terms, users and custom tags as you see fit.
Use your own tags
if you want to have your own way of clearing your build array add your custom unique tag in the build array (any unique string will do)
public function build() {
    return array(
        '#markup' =&gt; MY_MODULE_awesome_dynamic_node_content(),
        '#cache' =&gt; [
            'tags' =&gt; ['MY_CUSTOM_UNIQUE_TAG'],
        ],
    );
}

and in your custom code logic call invalidateTags with your own tag
function MY_MODULE_custom_clear_cache_logic(){ 
    ...
    \Drupal\Core\Cache\Cache::invalidateTags(array('MY_CUSTOM_UNIQUE_TAG'));        

if you want to read more about drupal 8 cache internals