The usual way to generate big primes is simply choose at random large numbers and test whether they are prime or not. The prime number theorem shows that you have a chance of about $\frac{1}{\ln n}$ to stumble on a prime that way, $n$ being your upper bound. In practice this can be (roughly) translated to "the number of failed attempts is the same order of magnitude as the number of digits in the prime you are attempting to generate", so a 2048-bit prime will take about 2,000 attempts even without any smart optimization - not that bad.
The main question is how to test that a number is prime. In practice, first attempt to divide by the first 100 primes or so. If that fails, run the Miller-Rabin test as it is very fast ($O(\ln ^3n)$). Miller-Rabin is probabilistic, so it might fail (tell you that a composite number is prime; never the other way around), but with the reasonable security parameters you can guarantee that the chance for an error is virtually nothing (even if you run Miller-Rabin for the rest of your lifetime, no error is expected).
If you must be 100% sure you have a prime, the AKS test will work, although it is much slower than Miller-Rabin. There are other methods of primality proving, such as the elliptic-curve test; they won't always work efficiently, but they're worth a try.
For further reading, try "Prime Numbers" by Crandall and Pomerance, which deals exactly with these topics.