I would like to ask about examples where experimentation by computers have led to major mathematical advances.
A new look
Now as the question is five years old and there are certainly more examples of mathematical advances via computer experimentation of various kinds, I propose to consider contributing new answers to the question.
I am aware about a few such cases and I think it will be useful to gather such examples together. I am partially motivated by the recent polymath5 which, at this stage, have become an interesting experimental mathematics project. So I am especially interested in examples of successful "mathematical data mining"; and cases which are close in spirit to the experimental nature of polymath5. My experience is that it can be, at times, very difficult to draw useful insights from computer data.
Summery of answers according to categories
(Added Sept, 2015)
To make the question a useful resource (and to allow additional answers), here is a quick summery of the answers according to categories. (Links are to the answers, and occasionally to an external link from the answer itself.)
1) Mathematical conjectures or large body of work arrived at by examining experimental data - Classic
The Prime Number Theorem; Birch and Swinnerton-Dyer conjectures; Shimura-Taniyama-Weil conjecture; Zagier's conjectures on polylogarithms; Mandelbrot set; Gosper Glider Gun (answer), Lorenz attractor; Chebychev's bias ; the Riemann hypothesis; the discovery of the Feigenbaum constant; Solving numerically the so-called Fermi--Pasta--Ulam chain and then of its continuous limit, the Korteweg--de Vries equation
2) Mathematical conjectures or large body of work arrived at by examining experimental data - Current
"Maeda conjecture"; the work of Candès and Tao on compressed sensing; Hankel determinants; Weari-Phelan structure; the connection of multiple zeta values to renormalized Feynman integrals; Thistlethwaite's discovery of links with trivial Jones polynomial; The Monstrous Moonshine; (link to the answer); Haiman conjectures on the quotient ring by diagonal invariants
3) Computer-assisted proofs of mathematical theorems
Kepler's conjecture ; a new way to tile the plane with a pentagon: advances regarding bounded gaps between primes following Zhang's proof; Cartwright and Steger's work on fake projective planes; the Seifert-Weber dodecahedral space is not Haken; the four color theorem, the proof of the nonexistence of a projective plane of order 10; Knuth's work on a class of projective planes; The search for Mersenne primes; Rich Schwartz's work; The computations done by the 'Atlas of Lie groups' software of Adams, Vogan, du Cloux and many other; Cohn-Kumar proof for the densest lattice pacing in 24-dim;
4) Computer programs that interactively or automatically lead to mathematical conjectures.
5) Various computer programs which allow proving automatically theorems or generating automatically proofs in a specialized field.
Wilf-Zeilberger formalism and software; FLAGTOOLS
6) Computer programs (both general purpose and special purpose) for verification of mathematical proofs.
The verification of a proof of Kepler's conjecture.
7) Large databases and other tools
Sloane's online encyclopedia for integers sequences; the inverse symbolic calculator.
Journal of experimental mathematics; Herb Wilf's article: Mathematics, an experimental science in the Princeton Companion to Mathematics, genetic programming applications a fairly comprehensive website experimentalmath.info ; discovery and experimentation in number theory; Doron Zeilberger's classes called "experimental mathematics":math.rutgers.edu/~zeilberg/teaching.html; V.I. Arnol'd's two books on the subject of experimental mathematics in Russian, Experimental mathematics, Fazis, Moscow, 2005, and Experimental observation of mathematical facts, MCCME, Moscow, 2006
Answers with general look on experimental mathematics:
Computer experiments allow new avenues for productive strengthening of a problem (A category of experimental mathematics).
There were many excellent answers so let's give the bounty to Gauss...