I think Lance's answer is a good approach. However, you could also use the message module (https://drupal.org/project/message). Messages are fieldable entities. You would:
Create a message type for tracking new tags (i.e. tag_added, or similar)
Add a field to store the tag created.
Use hook_taxonomy_term_insert() to catch the event and create a new message (you could probably use a rule instead if you prefer)
Build a view to show tag_added messages (or use the built-in, generic view that message ships with)
This is a more generic approach that would make sense if you also want to track other events or activities on your site (new users, new content, modified content, etc). One advantage is that you'd also collect the user info for each new tag.