Why would regression coefficients be different on a subsample? If I'm running a linear regression for example, and I take out some points, wouldn't the same line/plane still fit the data? If not, wouldn't that show that the data doesn't have a linear relationship?
Example: https://ocw.mit.edu/courses/economics/14-382-econometrics-spring-2017/lecture-notes/MIT14_382S17_lec1.pdf. On page 10, in the gender wage gap example, it finds a predictive effect of ~20% in the full sample and ~7% in the never married sample. But then if dWage/dGender depends on Marital Status, how can the functional form be right?
If I'm running a linear regression for example, and I take out some points, wouldn't the same line/plane still fit the data?

Aside from special cases no, OLS fits a line that is created based on minimization of sum of squared errors:
$$\min \sum e_i^2 = \min \sum (y_i-\hat{y_i})=\min \sum (y_i - \mathbf{x}_i^{\prime}  \beta)^2 .$$
If you remove some observations then you will likely change the objective function above leading to some other line having the best fit through data (save for special cases like when all observations are on a single line).

If not, wouldn't that show that the data doesn't have a linear relationship?

Not necessarily, the linear relationship is assumed to exist between the variables in the 'background', but since we cannot directly observe the data generating process and there will always be some disturbance term even if we are sure there should be a linear relationship between the two variables the observations will not necessarily all fall on a single line.
Non-linearity cannot be detected just from the fact that line you fit changes when you remove some data (although that is an indicator of robustness of a result - robust results should not change too much when sample is expanded/cut slightly). However, you can detect non-linearity in other ways. For example, you can look for patterns in residual plot. If residual plot shows some curved pattern then that is an indicator of potential non-linearity. There are also rigorous tests for non-linearity (like Ramsey test etc) but to go over all of such ways would be beyond the scope of an SE answer - you can read more about them in econometrics textbooks such as Wooldridge Introductory Econometrics: A Modern Approach.