in the implementations of VLAs that store the array on the stack, do they store the size of the array somewhere at runtime?

sizeof reports the sizes of VLAs, which are known only at runtime, so it must be possible to evaluate VLA sizes at runtime. Regardless of where a VLA is stored, then, if and as long as there is a potential for an lvalue designating that array to be the operand of a sizeof operator, either the VLA's size or an equivalent must be preserved somewhere in the program's state.

Moreover, during the lifetime of a VLA, the program must ensure that it does not use its storage for anything else. That does not necessarily require tracking a direct equivalent of its size, but certainly something related must be stored, if only as, say, the value of the stack pointer.

If yes, where?

It's unlikely that different implementations are wholly consistent about the details, but VLAs can be declared only at block scope, so with automatic storage duration. Given that, and the fact that there is no defined way to access an object containing their size, it is plausible that an implementation would satisfy a need to preserve VLA sizes with the same kind of storage that they would an automatic variable with register storage class. That does not necessarily mean a CPU register as the storage, but that's one possibility. The stack is another possibility. An indirect representation such as in the value of the stack pointer is another. On the other hand, where there is no chance that the size could be required by a sizeof expression, it might not be preserved in a recoverable manner at all.

If not, how do you know at runtime how much to decrement the stack pointer once the array goes out of scope?

In a typical stack-based machine, a called function does not rely on tracking the number of bytes of stack it is using so as to be able release that memory. Rather, it has the address of the start of its stack frame (the stack base), and on termination, it adjusts the stack pointer to equal its base pointer. The caller's own stack base will be restored as well, in a manner specific to machine architecture and calling convention.

Note: The same question also applies for alloca.

alloca() is a GNU extension, not part of standard C. It is distinguished from the VLA case by not engaging any special sizeof behavior that would require the size of the allocated object to be recoverable at runtime. However, it places the same requirement that the implementation needs to retain enough information to avoid using the allocated object's storage for anything else during that object's lifetime. That might be stored in any of the ways discussed for VLAs, but it is more likely to take a form that does not afford recovering the exact size.