Finding Large Primes
How do you start finding large primes? That depends on you, on what you know and on what you want. For example, you can download a program and then either join an existing project or take off on your own; or you might write your own program. We briefly explain each of these options further below.
When seeking primes, you must first decide what type of prime you want. The primes found to set size records are usual prime for which the classical primality tests work well--that means primes with forms like N = a.bn±1 (the classical tests require one of N±1 to factor substantially). But you can also seek to prove smaller, but more difficult numbers prime--numbers N for which N±1 do not factor easily. These records are much smaller, and much harder to find.
Downloading a Program
If you want to set a record for the largest known prime, and are looking for a long shot and a big monetary prize, then the best starting place might be to join a project like George Woltman's Great Internet Mersenne Prime Search (GIMPS). The chance of finding the next record is minute, but could be rewarding (e.g., there are large cash prizes)! The GIMPS site provides all you need to get started. You might also explore other of the top projects by score--we keep a list!
If you just want to get your name "in the books" by finding a prime that makes the list of the 5000 largest known primes, then consider Jean Penné's LLR. This program has proven thousands of primes and at times has accounted for the majority of the primes on the list. However, such programs usually work best when used as a sieve, and if you need help with that, again consider the projects. Just watch the list of top 20 programs to see what folks are using and always talk with others involved in the searches.
If you have a prime in mind, one that is not ammeniable to the classical tests, Marcel Martin's Primo (formerly Titanix) is one of the best implementations of ECPP around. It is easy to install and use on Windows machines.
But this is just the tip of the iceberg. See our Prime Links++ for more programs. Talk to others who are involved in searching for primes... The approach to take is as individual as you are!
Writing your Own Program
This approach offers freedom, but freedom can be expensive. You will need to understand both the mathematics of primality proving and the secrets of fast arithemtic on large numbers. Be sure to talk to others.