Can't someone luck out and jumble a bunch of numbers and letters, luck across a private key, and steal all the money off the paper wallet?
Depends on how the private key was generated. The official bitcoin client uses the openssl library to generate the keys, which is supposed to contain enough entropy that key generation is truly random. However, if you have an unsecure implementation for key generation, in principle someone could recreate the specific condition under which the key was generated and thus come across the same key, because key generation is a deterministic process.