One possible source for a Spanish sim card is Ebay. I checked out the other sites for sim cards, and they seem to charge a premium.
I bought a used Vodaphone sim card on ebay for around $30 and it's got about $10 euros of credits on it...supposedly. I won't know until I get to Spain and pop it in my phone, but the seller had a good rating.
Otherwise, I read that you can easily purchase a pre-paid sim card when you get to Spain. The benefit of having it before you leave is that there's a phone number that you can leave with friends/family for emergencies.
And, based on my research, in order for you to be able to interchange sim cards from different providers, your phone does have to be unlocked. If you purchased your phone from a cell phone provider (T-Mobile, Cingular/AT&T), they're usually locked to their network, despite their advertisement as "World Phones". I believe it just means that they're tri-band or quad-band and will work on their network or another network which they have a partnership with using the same sim card. In other words, it'll work, but, as posted, you pay the higher rates. If your phone is locked, I have read that some of the companies will unlock your phone for you, but only after you've been on their network for some amount of time. There are also third parties who will do it for you or sell you codes so that you can do it yourself. I haven't done it or had it done, but I have read that unlocking locked phones can cause you to loose some of the programming on the phone. I'm not sure how much truth there is to that though.
There are also websites that sell factory unlocked phones. The catch is that they're more expensive because you're not buying it with a plan so the phone company isn't subsizing the cost of the phone. I have found a site that sells phones with plans (mobilebee.com) and I considered buying a phone with them because I wanted a new camera phone, but I weighed the cost and decided to spend the extra $ on my trip instead. I bought a used unlocked phone instead...again from Ebay
...because it was cheaper. If you want to buy an unlocked phone to use in the States, Spain and around the world, be sure that it's either a tri-band or a quad-band.