For fiction: A bunch of books by Amy Krouse Rosenthal (Spoon, Exclamation Mark, Little Pea/Little Oink/Little Hoot, This Plus That, Wumbers), Stuck by Oliver Jeffers, Penrose the Mathematical Cat (for mathy kids), We just found a really cool book called The Numberlys by William Joyce...he also wrote The Fantastic Flying Books of Morris Lessmore, which is fabulous. Math Curse (and Science Curse, to a lesser extent) by Jon Scieszka. If I think of any more I'll add them later.
We also like a lot of non-fiction over here, examples being the scholastic read-about-science books.