I just realised that I cannot add tags to my API:Gateway-stage using CloudFormation templates. However, it’s possible to tag using the command line. But this requires knowledge of the id of the stage - which you don’t get when you use the !Ref function on the Stage.

But luckily it can be constructed easily:

aws apigateway tag-resource --resource-arn arn:aws:apigateway:<REGION-NAME>::/restapis/<RESTAPI-ID>/stages/<STAGE-NAME> --profile <PROFILE-NAME> --tags sometag=somevalue,anothertag=anothervalue

Perhaps this helps someone.