Does "finitely presented" mean "always finitely presented"? (Answered: Yes!)
$\require{begingroup} \begingroup$ $\def\coker{\operatorname{Coker}}$ $\def\im{\operatorname{Im}}$
Suppose that we have a short exact sequence $0 \to K \to R^m \to M \to 0$ with $K$ finitely generated over $R$ and that $0 \to K' \to R^n \to M \to 0$ is another short exact sequence. Your question is: is $K'$ necessarily finitely generated?
The answer is yes and we can see this as follows:
First, we argue for the existence of a commutative diagram
$$ \require{AMScd} \begin{CD} 0 @>>> K @>>> R^m @>>> M @>>> 0 \\ @. @VV{\tilde{f}}V @VV{f}V @| \\ 0 @>>> K' @>>> R^n @>>> M @>>> 0 \\ \end{CD} $$
Using the fact that free modules are projective we can lift the identity map $M = M$ to an $f\colon R^m\to R^n$ which makes the right hand square commute. Restricting $f$ to a map $\tilde{f}\colon K → K'$ fills in the last square and so we have the diagram as claimed.
Now using Snake's lemma we find that there is an isomorphism $\coker{\tilde{f}} \cong \coker{f}$. Thus We have a short exact sequence; $$ 0\to \im{\tilde{f}}\to K'\to \coker{f}\to 0. $$ Since $K'$ is squeezed between two finitely generated $R$ modules, it follows (by a well-known-fact) that $K'$ is itself finitely generated.
$\endgroup$
There's a famous quote, I think due to Szego, that a technique which can be used once is a trick, but if you can use it twice then it is a method. In that spirit, here is the EGA method which is very very useful to kill all such problems by reducing to the noetherian case. One can easily extrapolate from this example how one might prove related results (such as for finitely presented algebras, in which case the module-theoretic arguments in the other answers may not apply so easily).
General Principle: If everything used can be "described" with only finitely many elements of the base ring, the objects all descend to a noetherian subring (such as $\mathbf{Z}$-subalgebra generated by the finitely many elements used in the "description") and if we increase it a bit the morphisms also descend (need to kill off some relations), and if we increase it some more we can also descend all "reasonable" properties (flatness, smoothness, radiciel, surjectivity, etc.). This last step is by far the most subtle (for things like flatness). In the end, it always comes down to the fact that if something vanishes in a direct limit then it vanishes somewhere always the way, and if a direct limit of rings is 0 then the rings eventually vanish (track whether or not $1 = 0$).
Worked example for finite presentation of modules:
Step 0: Choose some right exact sequence $F' \stackrel{f}{\rightarrow} F \rightarrow M \rightarrow 0$ with $F$ and $F'$ finite free over $R$, and another surjection $\pi:P \twoheadrightarrow M$ from another finite free module to $M$. We wish to prove $\ker \pi$ is finitely generated.
Step 1: Observe that the map $f$ involves only finitely many elements of $R$ (think of a matrix), and likewise each basis vector in $P$ goes to an element of $M$ which lifts to something in $F$, so again that only involves finitely many elements of $R$ (to describe these lifts in $F$). Let $R_0 \subset R$ be the $\mathbf{Z}$-subalgebra generated by the elements of $R$ we just mentioned.
Step 2: Consider the $R_0$-linear map $$f _0 : F' _0 \rightarrow F _0$$
between finite free $R_0$-modules given by "the same matrix" as for $f$, so $R \otimes_{R_0} f_0 = f$. Let $M_0 = {\rm{coker}}(f_0)$, so by right-exactness (!) of tensor product, $M_0$ is an $R_0$-descent of $M$. Now $f$ has done its work and we forget about it.
Step 3: We can likewise define a map $\pi_0: P_0 \rightarrow M_0$ from a finite free $R_0$-module so that scalar extension to $R$ is $\pi$. If $\pi_0$ were surjective, then right-exactness of tensor product would imply that ${\rm{ker}}(\pi)$ is a quotient of $R \otimes_{R_0} {\rm{ker}}(\pi_0)$, the latter being finitely generated since $R_0$ is noetherian. Is $\pi_0$ surjective? Maybe not. But no big deal: if it becomes surjective after scalar extension to a bigger noetherian subring of $R$ then we can rename that as $R_0$ and proceed as above.
The issue is whether ${\rm{coker}}(\pi_0)$ vanishes. By right exactness (!) of tensor product, formation of this cokernel commutes with scalar extension to intermediate rings between $R_0$ and $R$. Scalar extension all the way to $R$ makes it vanish (since $\pi$ is surjective), so by expressing $R$ as a direct limit of finitely generated $R_0$-subalgebras $R_i$ we conclude that each of the finitely many generators of ${\rm{coker}}(\pi_0)$ have vanishing image after scalar extension to some common such $R_i$. Rename that as $R_0$.
QED
See EGA IV$_1$, 1.4.4 for the variant for finitely presented algebras. Well, better to first work it out for yourself. And then prove a module-finite algebra over a ring is finitely presented as a module if and only if it is finitely presented as an algebra. (This is not a tautology.) This may be a bit trickier to figure out, but good exercise. Solution in EGA IV$_1$, 1.4.7.
This is more or less the same as Andy's answer, but I'll say it differently. Suppose 0-->A-->Rp-->M-->0 and 0-->B-->Rq-->M-->0 are two exact sequences. Then we can form an exact sequence
0-->K-->Rp+Rq-->M-->0
where the thing in the middle is a direct sum, and the map to M is the sum of the two surjections. Then you can show there are isomorphisms K <--> A+Rq and K <--> B+Rp; these get produced using lifts Rp--> Rq and Rq--> Rp of the maps to M. Then A is finitely generated if and only if B is.