After a ton of research on the topic I was unsatisfied with nearly all of the "set it up in advance" international SIM options. As much as it scared me, I ended up going with the option in Greece of just going to the Germanos cell phone store in the Athens Airport (who is a dealer for Cosmote, one of their big cell providers). They provided a micro-SIM for my iPhone 4S (which I had unlocked already in the states), and I loaded 13 euro worth of credit on it, which gave me 200 minutes to anywhere in Greece, and 500MB of data, which was plenty for my stay.
It took a few minutes to negotiate what I needed through the slight language barrier, but the whole process only took about 20 minutes, and was far cheaper than anything that involved the convenience of setting it up here in the states. Prepaid cell phone plans are much more popular internationally than in the US (where we are addicted to postpaid contracts), so there are usually LOTS of options.
I think the process, generalized for most international travel would be:
- Find the largest few mobile providers in the country you are going to.
- Look at their websites to learn about some promotions (extra data if you add 5 euro this month!)
- Print a Google Map of a corporate store at the airport or close to your hotel.
- Drop in, get a SIM, and add some credit for the minutes/data you need.
- Bring your passport, some countries require a scan of your passport before they can issue a phone number to an international customer (such as Greece).
P.S. Be slightly wary of "kiosks". They can usually sell you a prepaid sim, but they usually can't activate it on the spot (they sell a bunch of SIMs through the day, then the next day someone from the company comes to activate them all). This means an activation delay, but more importantly, since you are travelling, there is no way to talk to anyone if the activation doesn't go correctly. If you are at a corporate store they can fix everything on the spot if there is an issue.
Kiosks are fine for buying the re-up cards - they are just a gift-card with a code on it that you text to the cell provider to add more minutes.