Prime numbers and their properties were first studied extensively by the ancient Greek mathematicians.

The mathematicians of Pythagoras's school (500 BC to 300 BC) were interested in numbers for their mystical and numerological properties. They understood the idea of primality and were interested in perfect and amicable numbers. 
A perfect number is one whose proper divisors sum to the number itself. e.g. The number 6 has proper divisors 1, 2 and 3 and 1 + 2 + 3 = 6, 28 has divisors 1, 2, 4, 7 and 14 and 1 + 2 + 4 + 7 + 14 = 28. 
A pair of amicable numbers is a pair like 220 and 284 such that the proper divisors of one number sum to the other and vice versa.
You can see more about these numbers in the History topics article Perfect numbers.
By the time Euclid's Elements appeared in about 300 BC, several important results about primes had been proved. In Book IX of the Elements, Euclid proves that there are infinitely many prime numbers. This is one of the first proofs known which uses the method of contradiction to establish a result. Euclid also gives a proof of the Fundamental Theorem of Arithmetic: Every integer can be written as a product of primes in an essentially unique way.

Euclid also showed that if the number 2ⁿ - 1 is prime then the number 2^n-1(2ⁿ - 1) is a perfect number. The mathematician Euler (much later in 1747) was able to show that all even perfect numbers are of this form. It is not known to this day whether there are any odd perfect numbers.

In about 200 BC the Greek Eratosthenes devised an algorithm for calculating primes called the Sieve of Eratosthenes.

There is then a long gap in the history of prime numbers during what is usually called the Dark Ages.

The next important developments were made by Fermat at the beginning of the 17^th Century. He proved a speculation of Albert Girard that every prime number of the form 4 n + 1 can be written in a unique way as the sum of two squares and was able to show how any number could be written as a sum of four squares.
He devised a new method of factorising large numbers which he demonstrated by factorising the number 2027651281 = 44021 × 46061.
He proved what has come to be known as Fermat's Little Theorem (to distinguish it from his so-called Last Theorem). 
This states that if p is a prime then for any integer a we have a^p = a modulo p. 
This proves one half of what has been called the Chinese hypothesis which dates from about 2000 years earlier, that an integer n is prime if and only if the number 2ⁿ - 2 is divisible by n. The other half of this is false, since, for example, 2³⁴¹ - 2 is divisible by 341 even though 341 = 31 × 11 is composite. Fermat's Little Theorem is the basis for many other results in Number Theory and is the basis for methods of checking whether numbers are prime which are still in use on today's electronic computers.

Fermat corresponded with other mathematicians of his day and in particular with the monk Marin Mersenne. In one of his letters to Mersenne he conjectured that the numbers 2ⁿ + 1 were always prime if n is a power of 2. He had verified this for n = 1, 2, 4, 8 and 16 and he knew that if n were not a power of 2, the result failed. Numbers of this form are called Fermat numbers and it was not until more than 100 years later that Euler showed that the next case 2³² + 1 = 4294967297 is divisible by 641 and so is not prime.

Number of the form 2ⁿ - 1 also attracted attention because it is easy to show that if unless n is prime these number must be composite. These are often called Mersenne numbers M_n because Mersenne studied them.

Not all numbers of the form 2ⁿ - 1 with n prime are prime. For example 2¹¹ - 1 = 2047 = 23 × 89 is composite, though this was first noted as late as 1536. 
For many years numbers of this form provided the largest known primes. The number M₁₉ was proved to be prime by Cataldi in 1588 and this was the largest known prime for about 200 years until Euler proved that M₃₁ is prime. This established the record for another century and when Lucas showed that M₁₂₇(which is a 39 digit number) is prime that took the record as far as the age of the electronic computer.
In 1952 the Mersenne numbers M₅₂₁, M₆₀₇, M₁₂₇₉, M₂₂₀₃ and M₂₂₈₁ were proved to be prime by Robinson using an early computer and the electronic age had begun.

By 2005 a total of 42 Mersenne primes have been found. The largest is M_25964951 which has 7816230 decimal digits.

Euler's work had a great impact on number theory in general and on primes in particular. 
He extended Fermat's Little Theorem and introduced the Euler φ-function. As mentioned above he factorised the 5^th Fermat Number 2³² + 1, he found 60 pairs of the amicable numbers referred to above, and he stated (but was unable to prove) what became known as the Law of Quadratic Reciprocity.
He was the first to realise that number theory could be studied using the tools of analysis and in so-doing founded the subject of Analytic Number Theory. He was able to show that not only is the so-called Harmonic series ∑ (1/n) divergent, but the series

¹/₂ + ¹/₃ + ¹/₅ + ¹/₇ + ¹/₁₁ + ...

formed by summing the reciprocals of the prime numbers, is also divergent. The sum to n terms of the Harmonic series grows roughly like log(n), while the latter series diverges even more slowly like log[ log(n) ]. This means, for example, that summing the reciprocals of all the primes that have been listed, even by the most powerful computers, only gives a sum of about 4, but the series still diverges to ∞.

At first sight the primes seem to be distributed among the integers in rather a haphazard way. For example in the 100 numbers immediately before 10 000 000 there are 9 primes, while in the 100 numbers after there are only 2 primes. However, on a large scale, the way in which the primes are distributed is very regular. Legendre and Gauss both did extensive calculations of the density of primes. Gauss (who was a prodigious calculator) told a friend that whenever he had a spare 15 minutes he would spend it in counting the primes in a 'chiliad' (a range of 1000 numbers). By the end of his life it is estimated that he had counted all the primes up to about 3 million. Both Legendre and Gauss came to the conclusion that for large n the density of primes near n is about 1/log(n). Legendre gave an estimate for π(n) the number of primes ≤ n of

π(n) = n/(log(n) - 1.08366)

while Gauss's estimate is in terms of the logarithmic integral

π(n) = ∫ (1/log(t) dt where the range of integration is 2 to n.

You can see the Legendre estimate and the Gauss estimate and can compare them.

The statement that the density of primes is 1/log(n) is known as the Prime Number Theorem. Attempts to prove it continued throughout the 19^th Century with notable progress being made by Chebyshev and Riemann who was able to relate the problem to something called the Riemann Hypothesis: a still unproved result about the zeros in the Complex plane of something called the Riemann zeta-function. The result was eventually proved (using powerful methods in Complex analysis) by Hadamard and de la Vallée Poussin in 1896.

There are still many open questions (some of them dating back hundreds of years) relating to prime numbers.
Some unsolved problems

1. The Twin Primes Conjecture that there are infinitely many pairs of primes only 2 apart.
2. Goldbach's Conjecture (made in a letter by C Goldbach to Euler in 1742) that every even integer greater than 2 can be written as the sum of two primes.
3. Are there infinitely many primes of the form n² + 1 ?
   (Dirichlet proved that every arithmetic progression : {a + bn | n ∊ N} with a, b coprime contains infinitely many primes.)
4. Is there always a prime between n² and (n + 1)² ?
   (The fact that there is always a prime between n and 2n was called Bertrand's conjecture and was proved by Chebyshev.)
5. Are there infinitely many prime Fermat numbers? Indeed, are there any prime Fermat numbers after the fourth one?
6. Is there an arithmetic progression of consecutive primes for any given (finite) length? e.g. 251, 257, 263, 269 has length 4. The largest example known has length 10.
7. Are there infinitely many sets of 3 consecutive primes in arithmetic progression. (True if we omit the word consecutive.)
8. n² - n + 41 is prime for 0 ≤ n ≤ 40. Are there infinitely many primes of this form? The same question applies to n² - 79 n + 1601 which is prime for 0 ≤ n ≤ 79.
9. Are there infinitely many primes of the form n# + 1? (where n# is the product of all primes ≤ n.)
10. Are there infinitely many primes of the form n# - 1?
11. Are there infinitely many primes of the form n! + 1?
12. Are there infinitely many primes of the form n! - 1?
13. If p is a prime, is 2^p - 1 always square free? i.e. not divisible by the square of a prime.
14. Does the Fibonacci sequence contain an infinite number of primes?

Here are the latest prime records that we know.

The largest known prime (found by GIMPS [Great Internet Mersenne Prime Search] in August 2008) was the 45^th Mersenne prime: M_43112609 which has 1209780189 decimal digits. The most recently discovered Mersenne prime (September 2008) is M_37156667. See the Official announcement

The largest known twin primes are 2003663613 × 2¹⁹⁵⁰⁰⁰ ± 1. They have 58711 digits and were announced by Vautier, McKibbon and Gribenko in 2007.

The largest known factorial prime (prime of the form n! ± 1) is 34790! - 1. It is a number of 142891 digits and was announced by Marchal, Carmody and Kuosa in 2002.

The largest known primorial prime (prime of the form n# ± 1 where n# is the product of all primes ≤ n) is 392113# + 1. It is a number of 169966 digits and was announced by Heuer in 2001.

___________________________________________________________________________________________________________________

1. B C Berndt, Ramanujan and the theory of prime numbers, Number theory Madras 1987 (Berlin, 1989), 122-139.
2. V N Chubarikov, Problems in prime number theory that are related to classical theorems of P L Chebyshev, Moscow Univ. Math. Bull. 46 (5) (1991), 15-19.
3. H Cohen, Les nombres premiers, La recherche 26 (278) (1995.), 760-765.
4. L E Dickson, History of the Theory of Numbers (3 volumes) (New York, 1919-23, reprinted 1966).
5. U Dudley, Formulas for primes, Math. Mag. 56 (1) (1983), 17-22.
6. U Dudley, History of a formula for primes, Amer. Math. Monthly 76 (1969), 23-28.
7. J Echeverria, Observations, problems and conjectures in number theory-the history of the prime number theorem, in The space of mathematics (Berlin, 1992), 230-252.
8. L J Goldstein, A history of the prime number theorem, Amer. Math. Monthly 80 (1973), 599-615.
9. A Granville, Harald Cramér and the distribution of prime numbers, Harald Cramér Symposium, Scand. Actuar. J. (1) (1995), 12-28.
10. S Das Gupta, The story of prime number, Ganita Bharati 16 (1-4) (1994), 37-52.
11. F Ischebeck, Primzahlfragen und ihre Geschichte, Math. Semesterber. 40 (2) (1993), 121-132.
12. F Manna, The Pentathlos of ancient science, Eratosthenes, first and only one of the 'primes' (Italian), Atti Accad. Pontaniana (N.S.) 35 (1986), 37-44.
13. L E Mauistrov, Prime values of the polynomial x²+x+41 (Russian), Istor.-Mat. Issled. 27 (1983), 63-67.
14. O Ore, Number Theory and Its History (1948, reprinted 1988).
15. J Pintz, On Legendre's prime number formula, Amer. Math. Monthly 87 (9) (1980), 733-735.
16. P Ribenboim, The little book of big primes (New York, 1991).
17. P Ribenboim, The book of prime number records (New York-Berlin, 1989).
18. W Schwarz, Some remarks on the history of the prime number theorem from 1896 to 1960, in Development of mathematics 1900-1950 (Basel, 1994), 565-616.
19. R de La Taille, Nombres premiers : 2000 ans de recherche, Science et vie 838 (1987), 16-20, 146.
20. H S Uhler, A brief history of the investigations on Mersenne numbers and the latest immense primes, Scripta Math. 18 (1952), 122-131.
21. A Weil, Number Theory: An Approach Through History from Hammurapi to Legendre (1984).