The following result is well-known. Solutions have even been posted on this site: $\gcd(2^{x}-1,2^{y}-1)=2^{\gcd(x,y)}-1.$ Let $d=\gcd(a,b)$. Then $\gcd(2a, 2b)=2d$, and therefore $\gcd((2^{2a}-1,2^{2b}-1)=\gcd((2^{a}+1)(2^a-1)\;,\;(2^b+1)(2^b-1))=2^{2d}-1.$ Since $d$ is odd, $2d$ divides $a$, and therefore $2^{2d}-1$ divides $2^a-1$. Note also that $\gcd(2^a+1,2^a-1)=1$ (unless $a=0$). Now we have all the pieces we need.
We are trying to prove that $\gcd(2^a+1,2^b+1)= 1$. Suppose to the contrary that the gcd is $>1$. Then there is a prime $p$ that divides both $2^a+1$ and $2^b+1$. Thus $p$ divides $\gcd((2^{a}+1)(2^a-1)\;,\;(2^b+1)(2^b-1))$, so $p$ divides $2^{2d}-1$. But $2^{2d}-1$ is a factor of $2^a-1$, so $p$ divides $2^a-1$.
Since $2^a+1$ and $2^a-1$ are relatively prime, $p$ cannot divide $2^a+1$, and we have our contradiction.