Reading through this article, I did not come to a conclusion right away, as the information here is stretched through multiple sources. I try to sum up all the findings from here (and linked source) as my personal testing to help others avoid the hunt.
Important to know is that each API always has a dedicated URL. The associated stages only get a separate suffix. Updating the deployment does not change the URL, recreating the API does.
API
├─ RestAPI (incl. Resource, Methods etc)
├─ Deployment
├─ Stage - v1 https://6s...com/v1
├─ Stage - v2 https://6s...com/v2
Relation stage and deployment:
To deploy AWS API Gateway through CloudFormation (Cfn) you need a RestApi-Cfn-Resource and a Deployment-Cfn-Resource. If you give the Deployment-Resource a stage name, the deployment automatically creates a deployment on top of the "normal" creation. If you leave this out, the API is created without any stage. Either way, if you have a deployment, you can add n-stages to a deployment by linking the two, but a stage and its API always has only one deployment.
Updating simple API:
Now if you want to update this "simple API" just consisting of a RestAPI plus a deployment you face the issue, that if the deployment has a stage name - it can not be updated as it already "exists". To detect that the deployment has to be updated in the first place, you have to either add a timestamp or hash to the deployment resource name in CloudFormation else there is even no update triggered.
Solving the deployment update:
To now enable updating the deployment, you have to split deployment and stage up into separate Cfn-Resources. Meaning, you remove the stage name from the Deployment-Cfn-Resource and create a new Stage-Cfn-Resource which references the deployment resource. This way you can update the deployment. Still, the stage - the part you reference via URL - is not automatically updated.
Propagating the update from the deployment to your stages:
Now that we can update the deployment - aka the blueprint of the API - we can propagate the change to its respective stage. This step AS OF MY KNOWLEDGE is not possible using CloudFormation. Therefore, to trigger the update you either need to add a "custom resource" our you do it manually. Other "none" CloudFormation ways are summed up by @Athi's answer above, but no solution for me as I want to limit the used tooling.
If anybody has an example for the Lambda update, please feel free to ping me - then I would add it here. The links I found so far only reference a plain template.
I hope this helped others understanding the context a bit better.
Sources: