Okay, let's see if I can explain this better.
Here is a token
It contains your vaccine info
along with some other techincal info, and finally a signature that can be used to verify that the information is correct. It's stored in this format, rather than the easier to read format, so you can easily stick it in a link for an app on your phone to open.
On the government servers, they have your vaccine information, along with a Private Key. This key is what they use to generate signatures, and involves a bunch of complex math. Basically Data + Private Key = Signature. Though it's important to note that you can't use the data + signature to calculate the private key.
When you got your QR code from the governemtn site, they use your data, sign it with the private key, and encode the whole token into the QR code.
On the app used by whoever is verifying your vaccine intormation is a Public Key. This key was generated by the government based on their private key and can be used to verify signatures. Given Data + Public Key + Signature and some complex math you can calculate if the data is valid. The public key is never enough to sign something, it's only ever able to verify a signature. For this reason its safe for the government to give out.
So somebody scans your QR code with their fancy app, they get the token, and the app uses their public key to verify that the data matches the signature. If the data was altered, but not the signature, they get an error because the signature doesn't match the data. If somebody alters the data and signs it with their own private key, then you still get an error because the public key can't verify signatures made with different private keys.
The website I linked,
jwt.io, is basically a sandbox for playing with and testing these types of tokens. It's how I was able to generate the example so easily. Since this is an open standard that a lot of the web runs on, there are a lot of libraries out there that do all the heavy lifting an complex math for you. I can go get whatever library that google or facebook uses, give it my user data and private key, and it will create the token for me. On my app I can use the same library and my public key to verify the data. There's more to it than just that for a proper and secure implementation, for example you need a good way to store your private keys so not everybody at your organization has access to them, but the government is likely to have most of that infrastructure in place all ready. So just generating some signed QR codes would be pretty straight forward.
Of course this is just one way that the data could be signed and verified. It's the one I'm most familiar with, and quite popular, but there are plenty of other formats as well.