Hi kelar419!
It all depends on WHERE in Spain you expect to go. If you want to go to Sevilla, for example, it may already be too late to have an easy time finding a place to sleep. It's easier in Madrid and Barcelona but keep in mind that MOST ALL Spaniards are moving around, traveling someplace during this weeklong holiday. Transportation can be difficult on buses and trains during the week for the same reasons.
How long in advance? Hard to say but I'd guess at least 1 month in advance. Anyone else have a different opinion? Feel free to voice it now!
Saludos, MadridMan