I've seen this fact stated (or alluded to) in various places, but never proved:
Let $n$ be a positive integer, let $m \in \{1,2,...,n-1\}$. Then $$\gcd(2^n-1, 2^m+1) = \begin{cases} 1 & \text{if $n/\gcd(m,n)$ is odd} \\ 2^{\gcd(m,n)}+1 & \text{if $n/\gcd(m,n)$ is even} \end{cases}$$
I've written up my own proof (see below), but I'm hoping to collect a few more. Any takers?
Also, information regarding generalizations would be very welcome!
Since $2^{2m}-1 = (2^m-1)(2^m+1)$, we have that
\begin{equation} \gcd(2^n-1,2^m+1) {\large\mid} \gcd(2^n-1,2^{2m}-1) = 2^{\gcd(2m,n)}-1 \end{equation}
(Some proofs of the equality can be found here, among other places.)
Case 1
If $n/\gcd(m,n)$ is odd, then $\gcd(2m,n) = \gcd(m,n)$, and so $\gcd(2^n-1,2^m+1)$ divides $2^{\gcd(m,n)}-1$, which in turn divides $2^m-1$. As $\gcd(2^m-1,2^m+1) = 1$, we conclude that $\gcd(2^n-1,2^m+1) = 1$.
Case 2
On the other hand, if $n/\gcd(n,m)$ is even, then $\gcd(2m,n) = 2\gcd(m,n)$, which implies that $\gcd(2^n-1,2^m+1)$ divides $2^{2\gcd(m,n)}-1 = (2^{\gcd(m,n)}-1)(2^{\gcd(m,n)}+1)$. As $\gcd(2^m+1, 2^{\gcd(m,n)}-1) = 1$, it must be that $\gcd(2^m+1,2^n-1)$ divides $2^{\gcd(m,n)}+1$. Now observe that $2^{\gcd(m,n)}+1$ divides both $i)$ $2^n-1$ and $ii)$ $2^m+1$.
Observation $i)$ follows from the fact that $2^{\gcd(m,n)}+1$ divides $(2^{\gcd(m,n)}+1)(2^{\gcd(m,n)}-1)=2^{2\gcd(m,n)}-1=2^{\gcd(2m,n)}-1$, which in turn divides $2^n-1$. Observation $ii)$ follows from the fact that $(2^{\gcd(m,n)}+1)(2^{\gcd(m,n)}-1)=2^{2\gcd(m,n)}-1=2^{\gcd(2m,n)}-1$ divides $2^{2m}-1 = (2^m+1)(2^m-1)$, which in turn implies that $2^{\gcd(m,n)}+1$ divides $2^m+1$.
We therefore conclude that $\gcd(2^n-1,2^m+1) = 2^{\gcd(m,n)}+1$.