For me, SEO is a technique then an art.
But if I need to choose which weighs more, if it's art or science.. I'll go with science, why? because it's the most boring subject for me which seems to be circulating on a certain point of view.
if it's an art then maybe I'll be too damn fond of doing it.
Combination between art and science.
It's not a science because we don't understand all of search engine secret like google.
It's not an art because search engine is built by mathematics algorithm.
Just Another Person
I think it is part art, science and voodoo.
The science part of it is the standards that are involved which will produce a predictable(within reason) result which is the definition of science.
Like search engine, directory and social site submissions.
The art comes in when you talk about sculpting your submissions in a way that look natural and create content that the search engines like.
The voodoo is things like comment posting or forum posting. You don't know if it will get you penalized or boosted in the serps with any certainty but you are still willing to shake a bone at it.
Anyway, that's my take on it.