Lemma. Let $G$ be a group, written multiplicatively, and let $H$ and $K$ be two subgroups. If $HK = \{hk\mid h\in H, k\in K\}$, then
$$|HK||H\cap K| = |H||K|$$in the sense of cardinalities.
Proof. Consider the map $H\times K\to HK$ given by $(h,k)\mapsto hk$. I claim that the map is exactly $|H\cap K|$ to $1$. Indeed, if $hk=h'k'$, then $h'^{-1}h = k'k^{-1}\in H\cap K$, so there exists $u\in H\cap K$, namely $u=h'^{-1}h$ such that $h=h'u$ and $k=u^{-1}k'$. Thus, $(h,k) = (h'u,u^{-1}k')$ maps to the same thing as $(h',k')$. Conversely, given $v\in H\cap K$, we have that $(h'v,v^{-1}k')\in H\times K$ maps to the same thing as $(h',k')$.
Thus, each element of $HK$ corresponds to precisely $|H\cap K|$ elements of $H\times K$. Thus, $|HK||H\cap K| = |H\times K| = |H||K|$, as claimed. $\Box$
Let $a$ and $b$ be integers, and consider $\mathbb{Z}/\langle ab\rangle$. This is a group with $|ab|$ elements. This group contains subgroups generated by $\gcd(a,b)$, by $a$, by $b$, and by $\mathrm{lcm}(a,b)$. $\gcd(a,b)$ generates the largest subgroup containing both $a$ and $b$; i.e., $\langle \gcd(a,b)\rangle = \langle a\rangle + \langle b\rangle$; while $\mathrm{lcm}(a,b)$ generates the smallest subgroup contained in both $\langle a\rangle$ and $\langle b\rangle$, i.e., $\langle \mathrm{lcm}(a,b)\rangle = \langle a\rangle\cap\langle b\rangle$. By the Lemma (with addition, since we are working in an additive group), we have:
$$|\langle a\rangle+\langle b\rangle| |\langle a\rangle\cap\langle b\rangle| = |\langle a\rangle||\langle b\rangle|$$
Now, the subgroup generated by $\gcd(a,b)$ has $\frac{|ab|}{\gcd(a,b)}$ elements; the subgroup generated by $\mathrm{lcm}(a,b)$ has $\frac{|ab|}{\mathrm{lcm}(a,b)}$ elements; that generated by $a$ has $\frac{|ab|}{|a|}$ elements, that generated by $b$ has $\frac{|ab|}{|b|}$ elements. Plugging all of that in it becomes
$$\gcd(a,b)\mathrm{lcm}(a,b) = |a||b|$$
which yields the desired equality.
$\Box$
This started as a partial solution, trying to bundle up what's been said in the comments and a bit more. After some more comments (esp. from Empy2) it is now a complete solution.
Proposition 1 gives an upper bound for the gcd. Proposition 2 then shows that this upper bound is actually assumed under certain conditions on $m,n$. Proposition 3 then shows that if those conditions are not fullfilled, the gcd is $1$.
Proposition 1:
$$\gcd(2^{m}+1,2^{n}+1) | 2^{\gcd(m,n)}+1.$$
Proof:
Let $d$ be a common divisior of $2^m+1$ and $2^n+1$.
We have $2^m+1|2^{2m}-1$ and $2^n+1|2^{2n}-1$, so it follows that $d|\gcd(2^{2m}-1,2^{2n}-1)$ and we know that
$$\gcd(2^{2m}-1,2^{2n}-1) = 2^{\gcd(2m,2n)}-1 = 2^{2\gcd(m,n)}-1 = (2^{\gcd(m,n)}-1)(2^{\gcd(m,n)}+1),$$
so
$$d|(2^{\gcd(m,n)}-1)(2^{\gcd(m,n)}+1). \tag{1} \label{eq1}$$
Let $p$ be a prime divisor of $2^{\gcd(m,n)}-1$. That means
$$2^{\gcd(m,n)} \equiv 1 \pmod p$$
and if we raise each side to the $\frac{m}{\gcd(m,n)}$-th power, we obtain
$$2^m \equiv 1 \pmod p \Longrightarrow 2^m+1 \equiv 2 \pmod p$$
Because $m > 0$, $2^m+1$ is odd, so $p \neq 2$ and hence $2^m+1 \neq 0 \pmod p$.
That means no prime divisor of $2^{\gcd(m,n)}-1$ can be a divisor of $2^m+1$, so $d$ and $2^{\gcd(m,n)}-1$ are coprime and we get from \eqref{eq1} that
$$d|2^{\gcd(m,n)}+1$$
and Proposition 1 follows.
Proposition 2:
When $m$ and $n$ contain the exact same power of $2$:
$$m=2^km', n=2^kn';\quad m'\equiv n'\equiv1 \pmod 2,$$
then
$$\gcd(2^{m}+1,2^{n}+1) = 2^{\gcd(m,n)}+1.$$
Proof:
In this case we also set $m'=\gcd(m',n')m''$ and $n'=\gcd(m',n')n''$ and find
$$2^m+1=2^{2^km''\gcd(m',n')}+1=\left(2^{2^k\gcd(m',n')}\right)^{m''}+1$$
and the equivalent for $n$:
$$2^n+1=2^{2^kn''\gcd(m',n')}+1=\left(2^{2^k\gcd(m',n')}\right)^{n''}+1.$$
Since $m''$ and $n''$ are odd, that means that $2^{2^k\gcd(m',n')} +1$ divides both terms (as per $(a+b)|(a^r+b^r)$ for any odd $r$).
Since $2^k\gcd(m',n') = \gcd(m,n)$, this proves Proposition 2.
The hard case seems to be when $m$ and $n$ contain different powers of $2$. I see no good way to attack that question in a general way, but maybe others do.
ADDED: It turns out that the comment by Empy2 below actually solves that problem, it just took me a while to realize that.
Proposition 3:
Let $m=\gcd(m,n)m'$ and $n=\gcd(m,n)n'$. If $m'$ is even and $n'$ is odd, then
$$\gcd(2^m+1,2^n+1)=1.$$
Proof:
The conditions on $m'$ and $n'$ are equivalent to $m$ and $n$ containing different powers of $2$, where I assumed w.l.o.g. that $m$ was the one containing the higher power of $2$.
We have ${\rm{lcm}}(m,n)=\gcd(m,n)m'n'$ so
$$2^{{\rm lcm}(m,n)}+1=2^{\gcd(m,n)m'n'}+1 =\left(2^{\gcd(m,n)m'}\right)^{n'}+1 = \left(2^{m}\right)^{n'}+1.$$
Since $n'$ is odd, we find that
$$2^m+1|\left(2^{m}\right)^{n'}+1 = 2^{{\rm lcm}(m,n)}+1.$$
Doing the same for $n$ we get
$$2^{{\rm lcm}(m,n)}+1=2^{\gcd(m,n)m'n'}+1 =\left(2^{\gcd(m,n)n'}\right)^{m'}+1 = \left(2^{n}\right)^{m'}+1.$$
We finally have
$$2^n+1|(2^n)^2-1|(2^n)^{m'}-1=2^{{\rm lcm}(m,n)}-1,$$
where the second divisibility follows because $m'$ is a multiple of $2$ (it was even).
So, as Empy 2 said, we have
$$2^m+1| 2^{{\rm lcm}(m,n)}+1,$$
$$2^n+1| 2^{{\rm lcm}(m,n)}-1,$$
so any common divisor of $2^m+1$ and $2^n+1$ must be a divisor of $2$. Since $m,n$ were both assumed to be positive, only $1$ can be a such common divisor.
Best Answer
Assume that you make a change by choosing $a$ nad $b$. WLOG if $a \leqslant b$, then $\gcd(a,b) \leqslant a \leqslant b \leqslant \text{lcm}(a,b)$. As $\gcd(a,b) \cdot \text{lcm}(a,b) = ab$, it is not hard to see that $\gcd(a,b)+\text{lcm}(a,b) > a+b$ in case of an actual change. This means that a change increases the sum of all the numbers on the board.
Now, assume that the numbers on the blackboard actually change infinitely often. For each change, we make the sum of the numbers on the board bigger since the sum of the GCD and LCM will be greater than the sum of the two numbers. However, if there are infinitely many changes, then the sum of the numbers will go off to $\infty$. Can this happen?
If the sum goes of to $\infty$, then the largest number must go off to $\infty$ as well. Obviously this is false as the product of all the numbers is constant and finite.