Why is the Fourier transform so ubiquitous? Many operations and equivalences in mathematics arise as some sort of Fourier transform. By Fourier transform I mean the following:
Let $X$ and $Y$ be two objects of some category with products, and consider the correspondence $X \leftarrow X \times Y \to Y$. If we have some object (think sheaf, function, space etc.) $\mathcal{P}$ over $X \times Y$ and another, say $\mathcal{F}$ over $X$, assuming the existence of suitable pushpull and tensoring operations, we may obtain another object over $Y$ by pulling $\mathcal{F}$ back to the product, tensoring with $\mathcal{P}$, then pushing forward to $Y$. 
The standard example is the Fourier transform of functions on some locally compact abelian group $G$ (e.g. $\mathbb{R}$). In this case, $Y$ is the Pontryagin dual of $G$, $\mathcal{P}$ is the exponential function on the product, and pushing and pulling are given by integration and precomposition, respectively. 
We also have the Fourier-Mukai functors for coherent sheaves in algebraic geometry which provide the equivalence of coherent sheaves on dual abelian varieties. In fact, almost all interesting functors between coherent sheaves on nice enough varieties are examples of Fourier-Mukai transforms. A variation of this example also provides the geometric Langlands correspondence
$$D(Bun_T(C)) \simeq QCoh(LocSys_1(C))$$
for a torus $T$ and a curve $C$. In fact, the geometric Langlands correspondence for general reductive groups seems to also arise from such a transformation. 
By the $SYZ$ conjecture, two mirror Calabi-Yau manifolds $X$ and $Y$ are dual Lagrangian torus fibrations. As such, the conjectured equivalence
$$D(Coh(X)) \simeq Fuk(Y)$$
is morally obtained by applying a Fourier-Mukai transform that turns coherent sheaves on $X$ into Lagrangians in $Y$. 
To make things more mysterious, a lot of these examples are a result of the existence of a perfect pairing. For example, the Poincaré line bundle that provides the equivalence for coherent sheaves on dual abelian varieties $A$ and $A^*$ arises from the perfect pairing
$$A \times A^* \to B\mathbb{G}_m.$$
Similarly, the geometric Langlands correspondence for tori, as well as the GLC for the Hitchin system, arise in some sense from the self-duality of the Picard stack of the underlying curve. These examples seem to show that non degenerate quadratic forms seem to be fundamental in some very deep sense (e.g. maybe even Poincaré duality could be considered a Fourier transform).
I don’t have a precise question, but I’d like to know why we should expect Fourier transforms to be so fundamental. These transforms are also found in physics as well as many other “real-world” situations I’m even less qualified to talk about than my examples above. Nevertheless I have the sense that something deep is going on here and I’d like some explanation, even if philosophical, as to why this pattern seems to appear everywhere. 
 A: From the point of view of engineering, sin and cos are eigenfunctions of LTI (linear time-invariant) systems, which makes the Fourier transform immanently important for system theory - and thus for control theory, signal processing and many other fields that make use of LTI systems
A: Another perspective on the connections among "Fourier" transforms and physical applications can be gleaned from the discussion in the MO-Q Explaining the Fourier-Mukai transform physically on constructive and destructive interference and the general relations among Green (or Green's) functions, associated convolutions/integral transforms, and impulse responses of a physical system as presented in the Wikipedia entry. A particularly far-reaching example of destructive and constructive interference in a superposition of elements of an eigenbasis is Huygen's principle. (For a quick intro to the connections between input and output of a system through convolutions and integral transforms, see Sec. 3.5, pp.53-65, of Mathemagics: A tribute to L. Euler and R. Feynman by Cartier on Heaviside's magic trilogy.)
More circuitously, on the differential/algebraic geometry side, the Laplace transform, a close relative of the classical Fourier transform with its own convolution theorem, is intimately related to compositional inversion and, therefore, the Legendre-Fenchel transform, both of which figure in Koszul duality of quadratic operads, diffeomorphism relations between quantum fields, the combinatorics of associahedra, cumulant-expansion theorems, free probability theory, and general algebraic geometry.  
A: I think this will be unexpected, but from the point of view of stereotype theory, Fourier transform is ubiquitous because it is an example of a general categorical construction -- envelope. This is a formal construction that describes in the language of category theory different mathematical operations of "taking nearest exterior of a given class" (in contrast to the dual construction of taking the "interior enrichment", which is called refinement). The examples of envelopes are


*

*the completion of a locally convex space,

*the Stone–Čech compactification of a topological space,

*the Arens-Michael envelope of a topological algebra, etc.
Fourier transform is also an example because in different "big geometries" it turns out to be a special case of the key envelopes used in the construction of these geometries. In particular, at the "branch of this tree" that can be called "topology" we obtain the following result:

for each locally compact abelian group $G$ the Fourier transform ${\mathcal F}:{\mathcal C}^\star(G)\to {\mathcal C}(\widehat{G})$ is a continuous envelope of the stereotype group algebra ${\mathcal C}^\star(G)$ of measures with compact support on $G$.

The same results are true in other big geometries: in differential geometry (with the smooth envelope as the key construction) and in complex geometry (with the Arens-Michael envelope, see details here and here). 
A: A signature property of the fourier transform is that it converts convolution into multiplication. (This is crucial for real world applications such as image processing especially as in the discrete case the fourier transform can be computed very quickly using the FFT).
Another signficant property of the fourier transform is that it measures how randomly a finite set is distributed via the size of its fourier coefficients.
This is applied in Roth's proof of Szemeredi's as one can show that if all the fourier coefficients of a set are small then the set has approximately the right number of arithmetic progressions of length three. 
Similarly, counting solutions to algebraic equations over finite fields uses the fact that the values of polynomials including simple powers are randomly distributed and this can be measured using the fourier transform and exponential sum estimates.
A: From the point of view of physics, Fourier transforms are ubiquitous because they are expansions in eigenfunctions of the derivative operator - and the derivative operator is fundamental in many aspects. Just to give two examples: The derivative operator is the generator of translations (in space or time), and to learn about the natural world, it is crucial that translations are symmetry operations - how would we learn about the natural world if we couldn't reproduce experiments at different times in different places? Secondly, field theories rely on locality, i.e., degrees of freedom only interact with their immediate neighbors - this naturally leads to dynamics described by derivatives.
A: To add a representation theory perspective: if $G$ is a Lie group, and $f$ is a function (or more precisely a distribution) on $G$ then (under certain mild conditions on $f$ and $G$), the function $f$ is uniquely determined by its unitary matrix coefficients, i.e. the coefficients of the matrix $\rho(f)$ where $\rho:G\to GL_n$ goes over all isomorphism classes of unitary and irreducible representations. This perspective should be understood as a change of basis that reveals the "underlying equivariant properties" of a function $f$, i.e. the properties important from the point of view of representation theory. 
Now the unitary irreducible representations of the additive group $\mathbb{R}$ are one-dimensional representations $\rho_\alpha: t\mapsto e^{i\alpha t}$ indexed by $\alpha\in \mathbb{R}$, and so the matrix coefficient decomposition of a function is precisely its Fourier transform. This hints that whenever you are interested in problems with additive equivariance (action by $\mathbb{R}$), you should expect to see Fourier transforms.
Your Fourier-Mukai example is an example of the same phenomenon "one category level higher". Namely, coherent sheaves over an algebraic group $G$ form a monoidal category under convolution. A partial analogue of "function $f$ on $G$ acts on line bundles the stack $BG$" (i.e. invertible representations) is "coherent sheaf $F$ on $G$ acts on gerbes on $BG$". In the case of abelian varieties, Gerbes on $BG$ are (more or less) the dual variety and the "matrix coefficients" of this action turn out to precisely be a change of basis (in this case, an equivalence of categories, now given by Fourier-Mukai). For nonabelian groups, the situation is more complicated, since it's not enough to consider gerbes, and it's tricky to say exactly what is an irreducible module category over a monoidal category... but for any reasonable extension of this picture you give there will always be a "matrix coefficient" functor.
