What's Variational Bayes?
Variational Bayes is a general technique for approximating posteriors in Bayesian inference.
Say that we have a posterior $P(\theta|X)$ that doesn't turn out to be a nice simple distribution, and we're interested in some aspect of that distribution, like its mean or some quantiles.
The prevailing technique is to use MCMC to generate a sample from that distribution, then to build sample estimators of the mean or quantiles.
Variational Bayes offers an alternative.
Instead of sampling from $P$, we're going to specify some family of distributions $\mathcal{Q}$ that are easy for us work with.
And we're going to pick some distribution in that family as a surrogate for $P(\theta|X)$.
For now, let's assume that we can parameterize the distributions in $\mathcal{Q}$ by some variational parameters $\eta$.
The word variational means "of, or related to optimization", and indeed the plan is to pick which $q_\eta\in\mathcal{Q}$ we want by solving an optimization problem:
$$ q_{\eta^*(X)}(\theta)= \underset{Q_\eta\in\mathcal{Q}}{\min} d[Q_\eta(\theta),P(\theta|X)]$$
where $d$ is some measure of dissimilarity between distributions.
Almost universally as of today, $d$ is the reverse KL loss, which is a divergence you can learn about by searching this site.
The idea is that if this distribution is a good enough approximation for the actual posterior, we could just ask it whatever questions we were going to ask $P(\theta|X)$. (This is only a profitable approach if $\mathcal{Q}$ contains distributions that are easy to work with wrt the posterior quantities of interest).
So what's Variational EM? Is it an EM algorithm in the style of Dempster? (No)
Historically, variational bayes has been popular in applications that involve latent variables.
These latent variables are treated identically to parameters in both Bayesian and variational Bayesian inference: we place a variational distribution over each latent variable just as we did parameter.
Let's call the latent variables $\mathbf{z}$; they have associated variational parameters $\eta_z$ (and we'll call those variational parameters associated with $\theta$ as $\eta_\theta$).
Many methods proposed for variational inference on latent variable problems alternate between optimizing $\eta_z$ for fixed $\eta_\theta$ and then vice versa, what are known in optimization as block coordinate descent methods (and actually oftentimes just plain-ol' coordinate descent, but let's leave that story for another day).
This reminded people of the Expectation Maximization algorithm which is/was prevalent for maximum likelihood based inference in latent variable models. We seem therefore to be cursed with the name Variational EM, despite the fact that there is no Expectation step: it's actually two "Maximize" steps (minimize if we consider KL divergence and maximize if we consider evidence lower bound) as we are taking descent steps on the variational distance between the current variational approximation and the true posterior in both steps.
(Oh, yes, to further confuse things, it turns out that under certain assumptions, the solution for our M steps may be expressed as an expectation...)