Is a product of Følner sets Følner? Let $G$ be an amenable (countable, discrete) group and let $F_1,F_2,...,F_n,...$ and $G_1,G_2,...,G_n,...$ be two Følner sequences. Is the product sequence (i.e. the sequence $(H_n)$ where $H_n$ is all elements of the form $f_ng_n$ for $f\in F_n, g\in G_n$) necessarily also a Følner sequence? If not, is this at least true for some nice class of groups (say, locally virtually nilpotent groups, or solvable groups or when the $F_i=G_i$ for all $i$? 
 A: some details added January 7th
It seems that the answer is "no" even for virtually abelian groups, and even
if $G_i$ is chosen by your arch enemy. The sequence $(F_i)_i$ can also be chosen rather freely in the proof. This answers some subquestions of the question, but not all of them. In particular do not know what happens if $F_i = G_i$ is required or if there are strong constraints on how fast the sets become invariant.

Suppose $G$ is a countable amenable group where some conjugacy class is infinite. Then for every Følner sequence $(G_i)_i$ there exists a Følner sequence
  $(F_i)_i$ such that $(F_iG_i)_i$ is not a Følner sequence.

Proof. Let $h$ have infinite conjugacy class, and $(G_i)_i$ be a Følner sequence. Since $h$ has infinite conjugacy class, for each $i \in \mathbb{N}$
there exists infinitely many $f_i \in G$ such that $f_i^{-1}hf_i \notin G_iG_i^{-1}$. Then $hf_iG_i \cap f_iG_i = \emptyset$, since otherwise $hf_ig_1 = f_ig_2$ for some
$g_1, g_2 \in G_i$ and thus $f_i^{-1}hf_i = g_2g_1^{-1} \in G_iG_i^{-1}$. Since there are infinitely many ways to choose $f_i$, we can also ensure $f_iG_i \cap G_i = \emptyset$.
Let now $(F_i')_i$ be any Følner sequence for $G$. For each $i \in \mathbb{N}$ pick maximal $\alpha(i) \leq i$ so that, writing $\chi_A$ for the characteristic function of a
set $A \subset G$, and $| \cdot |$ for the $\ell^1$-norm, we have
$$ |\chi_{F_{\alpha(i)}' G_i} - \chi_{G_i}| < 1/(\alpha(i) + 1) |G_i|. $$
Since $(G_i)_i$ is Følner, $\alpha(i)$ tends to infinity with $i$, so $(F_{\alpha(i)}')_i$ is a Følner sequence (using the definition of the asker).
Define $F_i = F_{\alpha(i)}' \cup \{f_i\}$. Obviously $(F_i)_i$ is a Følner sequence since the new element can contribute at most $2$ to the symmetric
differences $|\chi_{gF_i} - \chi_{F_i}|$. With the shorthand $o(|G_i|)$ for $\ell^1$ functions $x$ with $|x/|G_i|| \rightarrow 0$ with $i$, and also for
its usual meaning for reals, we have (by the properties of $f_i$ chosen in the first paragraph)
$$ \chi_{F_iG_i} = \chi_{f_iG_i} + \chi_{F_{\alpha(i)}' G_i} - \chi_{f_iG_i \cap F_{\alpha(i)}' G_i} = \chi_{f_i G_i} + \chi_{G_i} + o(|G_i|) $$
By $f_iG_i \cap G_i = \emptyset$, we then have $|\chi_{F_iG_i}| = 2|G_i| + o(|G_i|)$.
We similarly have
$$ \chi_{hF_iG_i} = \chi_{h f_i G_i} + \chi_{h G_i} + o(|G_i|). $$
Using these equalities, the fact $G_i$ is a Følner sequence, and the inverse triangle inequality, we get
$$ |\chi_{hF_iG_i} - \chi_{F_iG_i}|  =  |\chi_{h f_i G_i} + \chi_{hG_i} + o(|G_i|) - \chi_{f_i G_i} - \chi_{G_i} - o(|G_i|)|
\geq  |\chi_{h f_i G_i} - \chi_{f_i G_i}| - |\chi_{h G_i} - \chi_{G_i}| - o(|G_i|) = 2|G_i| - o(|G_i|). $$
This gives $\frac{|\chi_{hF_iG_i} - \chi_{F_iG_i}|}{|\chi_{F_iG_i}|} = \frac{2|G_i| - o(|G_i|)}{2|G_i| + o(|G_i|)} \rightarrow 1$,
and thus $(F_iG_i)_i$ is not a Følner sequence.

The infinite dihedral group admits Følner sequences $(F_i)_i$ and $(G_i)_i$ such that $(F_iG_i)_i$ is not a Følner sequence.

Proof. Every element of finite order has an infinite conjugacy class.
original
Not a solution but too long for a comment.
I think it's not necessarily Følner, as long as you can find a Følner sequence $G_i$ such that for some fixed $\epsilon > 0$ and $h \in G$,
for all $i$ there exist arbitrarily large $g$ such that $|hgG_i \setminus gG_i|/|gG_i| > \epsilon$. I imagine can happen in the non-abelian case, and it happens on the Heisenberg group.
Here's the idea of the construction. Pick $G_i$ such a Følner sequence. For each i construct $F_i$ like so: Pick a tiny set $F_i'$ around the
identity, containing the identity, in such a way that $F'_iG_i = G_i \cup A_i$ where $|A_i|$ is much smaller than $G_i$ (using that $G_i$ is Følner) and so that $F_i'$ itself is a Følner sequence.
Now, recall our assumption was that $gG_i$ is not a very left Følner-ish set for infinitely many g and a fixed translation $h$. So pick a couple of such $g$ and add them to $F_i'$ to get $F_i$. As long as we pick
much fewer than the cardinality of $F'_i$, $F_i$ will also be a Følner sequence.
But if we pick at least $\ell$ such $g$, then
if we pick them very separated from each other, $F_iG_i$ will actually consist of $F'_iG_i \approx G_i$ plus some disjoint
$gG_i$'s. If you pick a random element of this $F_iG_i$, it's going to be one of the $gG_i$ with probability roughly $(\ell-1)/\ell$ once $i$ is large (and $\ell$ can grow to infinity with $i$), and then with probability at least $\epsilon > 0$ the $h$-translate gets outside $gG_i$ (and by picking $g$ separated enough, we can make sure they don't hit any of the other $g'G_i$ either). So we don't even get a left Følner sequence for $h$-translations.
On the Heisenberg group, $G_i$ can be any Følner sequence:
Consider Heisenberg with generators $x$, $y$ and $z = [x, y]$, and any Følner sequence $G_i$. Consider $g = x^j$ and $h = y$. Since $h g G_i = g h z^j G_i$
we have $h g G_i \cap g G_i \neq \emptyset \implies h z^j G_i \cap G_i \neq \emptyset$ which means
$hz^j \in G_iG_i^{-1}$, which happens only for finitely many $j$.
So for the Heisenberg group, the answer is that the product is not necessarily Følner.
