Is the visa cancelled immediately? If so, how?
It doesn't matter whether the visa is cancelled at all. It can't be used because the former employee no longer meets the conditions for admission in H-1B status. This applies to any nonimmigrant status: you need a visa of the correct type (with some exceptions) and you need to meet certain criteria.
The question seems to assume that the former employee could legally return to the US if only it were possible to reach the border before the government manages to cancel the visa, but that is simply not how US immigration law works. A visa is not a license to enter the US. It is permission to travel to a US port of entry and apply to an immigration officer for admission. For the application to succeed, you need to meet the criteria for the status you seek, and with an H-1B visa one of those criteria is to be employed.
Look at any other criterion for admission. Suppose for example that you have a valid visa, perhaps B-2, but your passport has expired, and you haven't yet received a new passport. Your visa has not been cancelled; it is perfectly valid, yet you cannot enter the US. Furthermore, your visa won't be cancelled, and you will be able to use it as soon as you get a new passport.
In fact, the Foreign Affairs Manual says:
Visa Remains Valid: A change in employment does not have an effect on an H-1B employee's currently valid visa. For information on the effect of the new petition on the applicant's unexpired visa, see 9 FAM 402.10-11(A) below.
That section begins
After changing H-1B employers in accordance with USCIS procedures for making such a change, an H-1B visa holder may continue to use their original H-1B visa for entry into the United States.
So, to answer your questions:
how quickly are they barred from entering the US?
They aren't barred from entering the US. They only become ineligible to enter in H-1B status. They can enter in some other status, and they can also restore their eligibility to enter in H-1B status by finding another appropriate job.
Is the visa cancelled immediately?
No.