A quick google search of "free 8 bit tile sets" came up with this:
http://www.pixelprospector.com/the-big- ... -graphics/
I haven't used the site before but it appears to be a list of other sites containing graphics for free use. I looked at a few of the links and they have some pretty cool images and the graphics are all supposed to be royalty free.