Solution:

Suppose an odd prime $p$ divides both $2^m + 1$ and $2^n - 1.$ From $2^m \equiv -1 \pmod p,$ the order of $2$ modulo $p$ divides $2m$ but not $m,$ so the order contains exactly one more factor of $2$ than $m$ does. The order also divides $n,$ so $n$ must contain strictly more factors of $2$ than $m:$ writing $v_2$ for the number of factors of $2,$ we need $v_2(n) \gt v_2(m).$

Conversely, if $v_2(n) \gt v_2(m),$ let $g = \gcd(m, n).$ Then $v_2(g) = v_2(m),$ so $m/g$ is odd and $2^g + 1 \mid 2^m + 1;$ also $2g \mid n,$ so $2^g + 1 \mid 2^{2g} - 1 \mid 2^n - 1.$ Hence the gcd exceeds $1$ exactly when $v_2(n) \gt v_2(m).$

Among $1, \ldots, 30$ the counts of numbers with $v_2 = 0, 1, 2, 3, 4$ are $15, 8, 4, 2, 1.$ The number of pairs with $v_2(m) \lt v_2(n)$ is $$15 \cdot 15 + 8 \cdot 7 + 4 \cdot 3 + 2 \cdot 1 = 225 + 56 + 12 + 2 = 295.$$