I understand the basic structure of variational autoencoder and normal (deterministic) autoencoder and the math behind them, but when and why would I prefer one type of autoencoder to the other? All I can think about is the prior distribution of latent variables of variational autoencoder allows us to sample the latent variables and then construct the new image. What advantage does the stochasticity of variational autoencoder over the deterministic autoencoder?
VAE is a framework that was proposed as a scalable way to do variational EM (or variational inference in general) on large datasets. Although it has an AE like structure, it serves a much larger purpose.
Having said that, one can, of course, use VAEs to learn latent representations. VAEs are known to give representations with disentangled factors  This happens due to isotropic Gaussian priors on the latent variables. Modeling them as Gaussians allows each dimension in the representation to push themselves as farther as possible from the other factors. Also,  added a regularization coefficient that controls the influence of the prior.
While isotropic Gaussians are sufficient for most cases, for specific cases, one may want to model priors differently. For example, in the case of sequences, one may want to define priors as sequential models .
Coming back to the question, as one can see, prior gives significant control over how we want to model our latent distribution. This kind of control does not exist in the usual AE framework. This is actually the power of Bayesian models themselves, VAEs are simply making it more practical and feasible for large-scale datasets. So, to conclude, if you want precise control over your latent representations and what you would like them to represent, then choose VAE. Sometimes, precise modeling can capture better representations as in . However, if AE suffices for the work you do, then just go with AE, it is simple and uncomplicated enough. After all, with AEs we are simply doing non-linear PCA.
 Early Visual Concept Learning with Unsupervised Deep Learning, 2016
Irina Higgins, Loic Matthey, Xavier Glorot, Arka Pal, Benigno Uria, Charles Blundell, Shakir Mohamed, Alexander Lerchner
 A Recurrent Latent Variable Model for Sequential Data, 2015
Junyoung Chung, Kyle Kastner, Laurent Dinh, Kratarth Goel, Aaron Courville, Yoshua Bengio
As stated in the previous answers it can be viewed as just a nonlinear extension of PCA.
But compared to the variational autoencoder the vanilla autoencoder has the following drawback:
The fundamental problem with autoencoders, for generation, is that the latent space they convert their inputs to and where their encoded vectors lie, may not be continuous, or allow easy interpolation.
That's, the encoding part in the above graph can not deal with inputs that the encoder has never seen before because different classes are clustered bluntly and those unseen inputs are encoded be to something located somewhere in the blank:
To tackle this problem, the variational autoencoder was created by adding a layer containing a mean and a standard deviation for each hidden variable in the middle layer:
Then even for the same input the decoded output can vary, and the encoded and clustered inputs become smooth:
So to denoise or to classify(filter out dissimilar data) data, a standard autoencoder would be enough, while we'd better employ variational autoencoder for generation.
TenaliRaman had some good points but he missed a lot of fundamental concepts as well. First it should be noted that the primary reason to use an AE-like framework is the latent space that allows us to compress the information and hopefully get independent factors out of it that represent high-level features of the data. An important point is that, while AEs can be interpreted as the nonlinear extension of PCA since "X" hidden units would span the same space as the first "X" number of principal components, an AE does not necessarily produce orthogonal components in the latent space (which would amount to a form of disentanglement). Additionally from a VAE, you can get a semblance of the data likelihood (although approximate) and also sample from it (which can be useful for various different tasks). However, if you just want likelihood, there are better (explicit, tractable) density models out there, and if you want to draw samples....well GANs or the explicit density models with exact likelihood are a better choice.
The prior distribution imposed on the latent units in a VAE only contributes to model fitting due to the KL divergence term, which the  reference simply added a hyperparameter multiplier on that term and got a full paper out of it (most of it is fairly obvious). Essentially an "uninformative" prior is one which individually has a KL divergence close to zero and doesn't contribute much to the loss, meaning that particular unit is not used for reconstruction in the decoder. The disentanglement comes into play on a VAE naturally because, in the simplest case of multi-modal data, the KL divergence cost is lower by having a unique latent Gaussian to for each mode than if the model tries to capture multiple modes with a single Gaussian (which would diverge further from the prior as is penalized heavily by KL divergence cost) -- thus leading to disentanglement in the latent units. Therefore the VAE also lends itself naturally to most data sources because of the statistical implications associated with it.
There are sparsity imposing frameworks for AE as well, but unfortunately I'm not aware of any paper out there that compares the VAE vs AE strictly on the basis of latent space representation and disentanglement. I'd really like to see something in that arena though -- since AEs are much easier to train and if they could achieve as good of disentanglement as VAEs in the latent space then they would obviously be preferred. On a related note, I've also seen some promise by ICA (and nonlinear ICA) methods, but the ones I've seen forced the latent space to be of the same dimension as the data, which is not nearly as useful as AEs for extracting high-level features.
Choosing the distribution of the code in VAE allows for a better unsupervised representation learning where samples of the same class end up close to each other in the code space. Also this way, finding a semantic for the regions in the code space becomes easier. E.g, you would know from each area what class can be generated.
If you need more in-depth analysis, have a look at Durk Kingma' thesis. It's a great source for variational inference.