It is not a science. It is also not about computers. :)
SICP lecture 1 -- http://www.youtube.com/watch?v=zQLUPjefuWA
But maybe it is a science: there are certainly a number of things in CS that yield facts about things like algorithms (Big O, etc).
I read other comments here that compare computer science to math, and it is not an unfair comparison. However, even amongst mathematicians, you will see something of an avoidance to associate math with science. Math is a framework of a sort, a way to think. When we are talking about how to think, we are talking about philosophy. Science has its own roots in philosophy, so it is not surprising that we see some grey areas here.
So let me rephrase it a little... When you learn Computer Science, you learn how to think.
People compare CS with engineering disciplines, but we find that there are a lot of methodology salesmen but few magic bullets. The problem with comparing computer programming (the practical side of CS) to engineering is that programming is very difficult to measure. We graduated from the idea of measuring lines of code. We have not figured out how to accurately measure a technique like TDD. We have an idea that code quality can rise when people pay attention to it, when people think about the problem; we can encourage this with code reviews, but we can do the same by encouraging developers to have a good night's sleep. We have conjured approximations for our measurements, but none of this has quite the feel of engineering. We are not building bridges, complete with a starting plan based on knowns and an execution.
Algorithms are not building blocks. They are possible solutions to specific problems. There is more than one solution, and the algorithms our professors taught us come with trade-offs. Recently on HN, there was an excellent article and discussion on the trade-off made by grep to improve string searches.
So you cannot just pick from your handy dandy book of algorithms, fit them together in a programming jigsaw, and expect results. The world of software is soft; requirements change, and systems change. It is extremely flexible in a way that other, more physical entities, such as bridges, are not.
In addition to thinking of CS as a philosophy, I favor thinking of CS as an art. I am communicating something to the computer, certainly, but in order to ensure that my code can be picked up by others or myself a year down the line, I must also dive into aesthetics. The code must be readable. It must make sense, must describe the problem, be expressed in such a way that humans can derive meaning from it. Thus is CS as much about beautiful design as it is about getting results.