How to let users subscribe and be notified (email) when certain type of content or taxonomy is created? I would like to notify users (by email) whenever a content type or taxonomy term they subscribed to is submitted.

I thought Rules may play a role in this but can't figure out how to let them subscribe to the content type/taxonomy term

Any ideas are welcome

I'm using Drupal 7
You could do the subscription by adding the taxonomie term to the user profile. If you don't have to many content types you could add it as a simple select list to the profile. This can be done at admin/config/people/accounts/fields. 

As you sugested you can use Rules to get triggered about creates/updates of content or taxonomy terms. You might have to implement custom rules conditions or actions in PHP in a custom module to get exactly what you need. Check the differen hooks to define your own rules conditions or actions. hook_rules_action_info and hook_rules_condition_info are the most interesting for you.

To lear how to build your own rules code you find many examples in Drupal core and contributed modules.