In many textbooks, when a Bayesian model is presented, such as a classic Normal-Normal model, there is some sort of brief mention that the trials must be exchangeable. I am wondering why this is necessary and what goes wrong if exchangeability doesn't hold. Does anyone have any concise answers?
Exchangeability is not necessary. There are Bayesian models in which observations are not exchangeable. For example, models for time-series analysis and forecast in weather prediction or finance. Generally speaking, in such models more recent observations are considered to be more relevant for inference about future ones; a sort of "fading memory". Exchangeability therefore cannot be assumed for them. There is a huge variety of non-exchangeable models; see the references below.
Exchangeable models are often easier to deal with, but they may be inappropriate. In fact, rather than "wrong" vs "right", the question is whether exchangeability or other assumptions, like the "fading memory" mentioned above, are more appropriate or reasonable for the inferences you're making, or computationally easier. We must often find a balance between these two aspects.
There's no "right" or "wrong" because there's no experiment that can tell us whether an inference model is "correct". This is the fundamental issue of induction, about which many, many authors have written; I recommend the works of Hume, Johnson, Jeffreys, de Finetti, Jaynes cited below. We can only apply a particular way of doing induction, formalized as a statistical model, and then see if we're satisfied with it or not. And this satisfaction depends on many criteria, many of which subjective.
Texts like Bernardo & Smith: Bayesian Theory (Wiley 2000) focus more on exchangeability, but as they themselves remark (§ 1.4.1), their book is not meant to cover all kinds of inferences in Bayesian probability theory. Texts specifically focused on non-exchangeable models are for example:
R. Prado, M. West: Time Series: Modeling, Computation, and Inference (CRC 2010) – this should be a good and recent starting point if you're already familiar with exchangeable models.
A. Pole, M. West, J. Harrison: Applied Bayesian Forecasting and Time Series Analysis (Springer 1994)
E. Greenberg: Introduction to Bayesian Econometrics (Cambridge 2008)
A. Zellner: An Introduction to Bayesian Inference in Econometrics (Wiley 1996)
G. L. Bretthorst: Bayesian Spectrum Analysis and Parameter Estimation (Springer 1988) http://bayes.wustl.edu/glb/bib.html
G. E. Box, G. M. Jenkins, G. C. Reinsel, G. M. Ljung: Time Series Analysis: Forecasting and Control (Wiley 2016), especially ch. 7
W. Palma: Long-Memory Time Series: Theory and Methods (Wiley 2007), especially ch. 8
See also the numerous references about time series that Bernardo & Smith give in § 5.6.5.
Regarding induction, some insightful texts are:
D. Hume: A Treatise of Human Nature: Being an Attempt to Introduce the Experimental Method of Reasoning into Moral Subject (Oxford 1896) https://archive.org/details/treatiseofhumann00hume_0, Book I, § III.VI
W. E. Johnson: Probability: the deductive and inductive problems, Mind 41 n. 164 (1932), 409–423
W. E. Johnson: Logic. Part II: Demonstrative Inference: Deductive and Inductive (Cambridge 1922) https://archive.org/details/logic02john, chapters VIII and following
W. E. Johnson: Logic. Part III: The Logical Foundations of Science (Cambridge 1924) https://archive.org/details/logic03john, the Appendix
B. de Finetti: Foresight: Its Logical Laws, Its Subjective Sources, in Kyburg, Smokler: Studies in Subjective Probability (Krieger 1980), pp. 53–118
B. de Finetti: Probability, Induction and Statistics: The art of guessing (Wiley 1972), chapter 9
H. Jeffreys: The present position in probability theory, Brit. J. Phil. Sci. 5 n. 20 (1955), 275–289
H. Jeffreys: Scientific Inference (Cambridge 1973), chap. I
H. Jeffreys: Theory of Probability (Oxford 2003), § 1.0
E. T. Jaynes: Probability Theory: The Logic of Science (Cambridge 2003) http://www-biba.inrialpes.fr/Jaynes/prob.html, http://omega.albany.edu:8008/JaynesBook.html, http://omega.albany.edu:8008/JaynesBookPdf.html, § 9.4
From the representation theorem, we know that exchangeability is essentially just an operational condition that is equivalent to the conditional IID form (which implies equicorrelation among the observable values). If this doesn't hold, it just means that there is some structure to the problem that is incompatible with the conditional IID form. This could be some kind of auto-correlation, or another order-based correlated form (as opposed to equicorrelation), or some other kind of effect involving statistical dependencies that are not equal among pairs of observables.