I use five strategies to pay for things when I travel:
The best rates are often the rates you get with your American credit card or debit card. Try to charge as much as you can. The fees are very low and the exchange rates are fair. However, many American banks charge several dollars for every foreign currency transaction, so if you plan to spend a lot of time in Europe, you may want to apply for a credit card with low or free foreign currency transactions. Right now, Capital One has a reputation for being the best deal on foreign currency.
My second favorite strategy is to get cash out of foreign ATMs using my own bank's debit card attached to my checking account. I've never had a problem with this, but I have heard that if your PIN is more than 4 digits, it may not work internationally. There are a few countries where most ATMs don't like American bank cards, notoriously Japan. In Japan, if you can find a post office, they have ATMs that are happy to accept American bank cards.
Any kind of transaction that involves a human being standing behind a counter changing money for you is going to be bloody expensive. Like, 15% expensive... or more. You have to pay for the person and the counter. I very rarely do this.
Very rarely, in Europe, you will find yourself dealing with an automatic machine that ONLY accepts credit cards and which keeps asking you for a PIN or refusing to read your American credit card. The most common places I've had this happen:
Automatic ticket machines at railroad stations
Bicycle rental machines
Unattended gas stations
Toll booths in France
Essentially what's happening here is that European credit cards have an embedded chip and require a PIN, while American credit cards use a magnetic stripe. In some situations in Europe you must pay with a Chip and PIN credit card. See this question for information about getting a chip and pin card as an American. There is some evidence that Chip and PIN cards will be widely available to US bankcard holders in Fall 2015.
- In a pinch, you'll discover that nicer hotels are often happy to convert money for you. The rates are not very good, but if you keep a few hundred dollars in US cash hidden away somewhere safe, it'll get you out of just about any kind of situation.