Is it incorrect terminology to say that data follows a t-distribution random walk, for example? Does the fact the increments have this underlying distribution mean it should be referred to as a markov chain (and random walk is just a type of mc with a uniform distribution of increments)?
Ultimately it depends on precisely what your definition of a random walk is, which may vary somewhat from person to person - terms mean what people understand them to mean. (If you have defined it in a particular way, that's what it means, though generally one should only defy broad conventions with very good reason.)
Most usually, a random walk doesn't restrict itself a particular distribution of increments (but Gaussian is very common and if unspecified, might usually be my first guess unless it appeared that the distribution would be discrete).
However, Bernoulli random walks, and other kinds of random walks do certainly exist.
For example, the Wikipedia article doesn't limit the distribution to any particular family (the Gaussian case has its own subsection there).
Here, as well, it is the case that the distribution would generally be expected to be specified, implying it could take other distributions. This accords with what is most usually seen, though it's not all that hard to find people in particular contexts dropping explicit mention of the distribution of the increments (it's usually obvious from context, however).
When describing large scale/long term behavior, the distribution of increments usually doesn't tend to matter quite so much (essentially because of the central limit theorem), though it can depend on the characteristics of the distribution of the increments, and precisely what is being computed for the random walk.
So, broadly speaking, yes, conventionally you can have independent t-distributed increments, and it's still a random walk. I'd expect most readers would be perfectly comfortable with the usage.