How does Mathematica do symbolic integration? I suppose there was at least once in our lifetime the point where we resorted  to mathematica for help with an integral.-Unless you chose not to have the pleasure of using the continuum in your mathematical field of research.
I am wondering however whether behind a computer algebra system like mathematica that does symbolic computations there is some high-level idea how it would approach an awkward integral and try to find an anti-derivative?-I focus here on the integration part, since I think I would understand how to implement symbolic differentiation, at least conceptually, but integration seems to be rather mysterious to me.
 A: An overview by one of the developers of Mathematica, focusing on definite integrals, is at Symbolic definite integration: methods and open issues.
Mathematica knows all the entries in Gradshteyn-Ryzhik, and more generally uses the Marichev-Adamchik Mellin transform to express the integral in terms of Meijer G functions, which are then simplified if possible. An example is worked out here.
A: Maple uses the Risch algorithm; see Keith Geddes and George Lebahn, Symbolic and numeric integration in Maple
A: People usually mention the Risch algorithm first, as other answers have.
Another approach, which is surprisingly successful, is to do what you or I would when solving integrals: look for patterns for which we have known-to-be-useful transformations.  RUBI (which is usable from Mathematica as well as from other systems) does precisely this. According to its benchmarks, it works better than Mathematica's built-in Integrate.
This is why I was not surprised to see that machine-learning methods can also work very well. While I did not read the paper, I imagine that the inherent unpredictability/unreliability of such methods is not an issue: the result can always be verified by differentiation.
(Note: All I wrote above applies to indefinite integration. Definite integration is a different animal, and much harder problem, mostly because it is necessary to verify that the function behaves nicely in the middle of the integration interval.)
A: One approach to symbolic integration is using representations as Holonomic functions (https://en.wikipedia.org/wiki/Holonomic_function): solutions to differential equations of the form:
$$p_r f^{(r)} + \cdots + p_i f^{(i)} + \cdots + p_0 f = 0$$ where the $p_i$ are polynomials.
Most functions you could want to antidifferentiate are holonomic, but not all (notably, not tan(x)).
Given such a representation (the list of polynomials), antidifferentiation is as simple as shifting the indices, so the problem comes down to translating to and from this representation.
Packages for working with holonomic functions are available for Mathematica and Maple
