As far as I can tell, the best way to get cellular/internet service for your unlocked GSM phone while in Spain is to head down to one of the ubiquitous Carrefour supermarkets and get a prepaid SIM card. I saw a variety of prices, like 10 Euro for a SIM card plus 10 Euro of credit on the account. We ended up paying 1EUR for the SIM card and putting 5EUR credit on it.
Calls are 0.08EUR/minute, but the best part is the internet access. After adding a "carrefourinternet" APN to my phone, 3g internet came right up. Their website has conflicting claims, but it appears that it costs either 0.50EUR/day for 20MB, or 1EUR/day for 100MB. Above that, it still works, but the rate is capped at 128Kb/sec, which still isn't bad. And for 19EUR, I can get 1GB of high speed connectivity on top of that, so that I don't hit the cap so much.
http://www.carrefour.es/telecom/internet-movil/index.html
Update: The Carrefour website is misleading. Apparently the 19EUR/1GB deal is only for USB cell modems. Instead I had to text "ALTA BONOPRE" to 22864, which buys 300MB for a month for 6EUR. And if it runs out, I think I can text "BAJA BONOPRE" to go back to 20MB/day.
