Vegetarian Food in Spain

I'm going on holiday to Southern Spain in a few weeks, and wondered if anyone can advise on what it's like for finding vegetarian food, especially when eating out. I've always imagined Spain to be a militantly carnivorous place, but I'll be happy to be proved wrong.

Tapas can work well - a fair bit will be meaty, but there should be enough veggie options too.

Thanks for the advice - that last link is absolutely brilliant.