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?

In a VAE both the encoder and the decoder assign to an input a distribution. You correctly stated that for the encoder, but this is also true for the decoder: for the same latent input $$\mathbf z$$ you will always get the same distribution (often normal, so it is described by the decoder output $$(\boldsymbol \mu, \boldsymbol\sigma^2)$$), but sampling from it will give you different $$\hat{\mathbf x}$$ for the same $$\mathbf z$$.