How can supervised learning be viewed as a conditional probability of the labels given the inputs?
This formulation/interpretation can indeed be confusing (or even misleading), as the output of a neural network is usually deterministic (i.e. given the same input $x$, the output is always the same, so there is no sampling), and there isn't really a probability distribution that models any uncertainty associated with the parameters of the network or the input.
People often use this notation to indicate that, in the case of classification, there is a categorical distribution over the labels given the inputs, but this can be misleading, as the softmax (the function often used to model this categorical distribution) only squashes its inputs and doesn't really model any uncertainty associated with the input or the parameter of the neural network, although the elements of the resulting vector add up to 1. In other words, in traditional deep learning, only a point estimate for each parameter of the network is learned and no uncertainty is properly modeled.
Nevertheless, certain supervised learning problems have a formal probabilistic interpretation. For example, the minimization of the mean squared error function is equivalent to the maximization of a log probability, assuming your probability distribution is a Gaussian with a mean equal to the output of your model. In this probabilistic interpretation, you typically attempt to learn a probability (e.g. of the labels in the training dataset) and not a probability distribution. Watch Lecture 9.5 — The Bayesian interpretation of weight decay (Neural Networks for Machine Learning) by G. Hinton or read the paper Bayesian Learning via Stochastic Dynamics or Bayesian Training of Backpropagation Networks by the Hybrid Monte Carlo Method by R. Neal for more details.
Moreover, there are Bayesian neural networks (BNNs), which actually maintain a probability distribution over each parameter of the neural network that models the uncertainty associated with the value of this parameter. During the forward pass of this BNN, the specific parameters are actually sampled from the corresponding probability distributions. The actual learnable parameters of a BNN are the parameters of these distributions. For example, if you decide to have a Gaussian distribution over each parameter of the neural network, then you will learn the mean and variance of these Gaussians.