I bought my niece a Kindle that just arrived and I'm about to load it up with books to give it to her tomorrow for her birthday. I've decided to be a sneaky uncle and include good books that can teach better abilities to think or at least to consider science cool and interesting. She is currently in the 4th Grade with 5th coming after the Summer.
She reads basically at her own grade level so while I'm open to stuffing the Kindle with books to be read when she's ready, I'd like to focus on giving her books she can read now. Ender's Game will be on there most likely. Game of Thrones will not.
What books would you give a youngling? Her interests currently trend toward the young mystery section, Hardy Boys and the like, but in my experience she is very open to trying new books with particular interest in YA fantasy but not much interest in Sci Fi (if I'm doing any other optimizing this year, I'll try to change her opinion on Sci Fi).
Within YA mysteries, my favorites as a child were The Three Investigators. They had more clever plots than the Hardy Boys and other series, and the protagonists did more actual deduction, observation and reasoning. Also, cameo appearances by Alfred Hitchcock! Sadly, they don't seem to be available for Kindle.
If she hasn't read it yet, you could give her Sherlock Holmes. Quite a lot of (19th century, but still) science and methodic reasoning, should be read before other classical mystery authors like Agatha Christie (because all were reacting to it), and with the bonus (for you) of it being out of copyright and so free for Kindle.
As for SF, how about Jules Verne? It is different enough from current day SF that if she might like it even if she has a prejudice against the latter (no spaceships, aliens, rayguns, etc), but teaches a deeper appreciation for science and scientific progress than most modern SF.