Thanks to the ever-excellent Man in Seat 61, I've found out that there are luggage lockers available at Barcelona's Sants main station:
Barcelona Sants has luggage lockers, open 05:30-23:00 daily. Small locker €3.60, large €5.20. There's an X-ray check of all bags entering locker area.
It has been a year or so since I last took the train from Sants, but I can't remember seeing any signs for luggage storage. I also recall it's a fairly large station.
Does anyone know exactly where in the station the luggage storage is, and/or if it is well sign-posted from inside the station?