Is it possible to change this example.com/tag:travel to this example.com/?tag=travel?
Grav does fully support the traditional URL queries, however any plugins and/or themes would need to be modified to look for a query value rather than a parameter as it’s doing now.
Could you provide an example for TwentyFifteen Site skeleton/theme? I’m new to coding in general so I’m having hard time finding the part which I have to edit.
This is not a trivial change. Your basically wanting to change how data is transferred between pages. Unless you have a good reason, I suggest that you leave the parameter style as it’s prettier and works fine as-is.
Search engines do not seem to support the default format so I want to change it to be compatible with this: https://support.google.com/webmasters/answer/6080550?hl=en and this https://www.bing.com/webmaster/help/ignore-url-parameters-d7496c65 Would appreciate any hints which part I need to edit to make this work 
The great thing is that search engines will treat the Grav parameters as part of a valid independent URL. So there’s no need for query support. This is not something you need to worry about.