How is the VAE encoder and decoder "probabilistic"? In a VAE, my understanding is that the encoder takes in $x$, outputs a vector $(\mu, \sigma)$ that characterizes a certain normal distribution $q(z|x)$. Then we sample from this distribution to get a latent vector $z$, which goes into the "probabilistic" decoder to produce a generated output $\hat{x}$, which is how now, not-seen-before images, for instance, are generated in these generative models. My question is where there is randomness/stochasticity outside of the sampling from the normal in the latent representation layer. That is to say, once you learn the parameters $\theta, \phi$ that characterize the encoder and decoder neural networks, the neural networks are -- like any other neural networks -- deterministic function approximators. I can see there being an argument for the encoder "encoding a distribution" since it learns to output a vector $(\mu, \sigma)$ that characterizes a distribution, but I see no similar argument for the decoder, which will output the same $\hat{x}$ for a fixed sampled $z$ in the latent space. Similarly, would the encoder output the same $(\mu, \sigma)$ for a fixed input $x$? If so, how can the encoder be called "probabilistic" either?

I think your view is correct, indeed the probabilistic nature of VAEs stems from parametrizing the latent distribution and then sampling from it. I would argue that this procedure influences the whole network, making them more capable of generalization but also more prone to noisy reconstruction (often seen in GANs vs VAE comparisons). Of course, this doesn't make the rest of the network inherently probabilistic (that would be a Bayes-NET, I think), as you noticed.
