For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$?

Is it guaranteed that there will be some $p$ such that $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$?

In other words, does each $2^x-1$ introduce a new prime factor?

Yes, it's true (except for $2^6-1=7\times 9$).

This is known as Bang's theorem, and is a corollary of Zsigmondy's Theorem.

You can find a proof here (Theorem 3).

This result is due to Zsigmondy (1892), with special cases $(b=1)$ (re)discovered by Bang (1886), Birkhoff & Vandiver (1904) ... see Ribenboim, The New Book of Prime Number Records, p. 43, 67-68, 338, 437. Vandiver, a prolific researcher on FLT = Fermat's Last Theorem, applied it to the first case of FLT and related diophantine equations, e.g. see Ribenboim's book 13 Lectures on Fermat's Last Theorem, pages 52,161,206,234,236.

Such results have many applications: a MathSciNet search on Anywhere=(Zsigmondy or (Birkhoff and Vandiver)) will find over 35 related Math Reviews. Schinzel (1974, MR 93k:11107) extended the theorem to arbitrary algebraic number fields $K$:

If $a$ and $b$ are algebraic integers in $K,\,$ $(a,b)=1,\,$ and $a/b$ is of degree $d$ and not a root of unity, then there exists $\,n_0 = n_0(d)\,$ such that for all $n > n_0,\,\ a^n - b^n\, $ has a prime ideal factor $P$ not dividing $\,a^m - b^m\, $ for all $ m < n$.

Later (1993, same MR) "he generalized this to show that every algebraic number which is not a root of unity satisfies only a finite number of independent generalized cyclotomic equations considered by the reviewer [in Structural properties of polylogarithms, Chapter 11, see p. 236, Amer. Math. Soc., Providence, RI, 1991; see MR 93b:11158]".

There are also elliptic and polynomial generalizations.