In 1670, Blaise Pascal published Pensees, which was a defense of the Christian religion. (It should be noted that this book was published after his death in 1662.)
In that book, he has a quote:
“There is a God-shaped vacuum in the heart of every person, and it can never be filled by any created thing. It can only be filled by God, made known through Jesus Christ.”
- Blaise Pascal, Pensees
Since then, the concept has taken on a life of it's own and the phrase has been found throughout many Christian circles. (Recently, in 2002, a book was published with the title 'God Shaped Hole'.)
While other answers show biblical support for this concept, the concept itself is actually a non-biblical one.