My DD still loves to collect autographs at 9, but her biggest "autographing" trip was when she was 4. She really wanted to see all the characters, even more than the attractions LOL. We bought a great book at WDW that had the princesses on the front, and then each page was a picture sleeve on one side and an autorgraph sheet on the other. We had each character sign one page, and then put DD's pic w/ the character on the facing page (when we got home, of course.) This is still DD's favorite souvie from any Disney trip ever! (She's been to WDW 4 times, DLP once, and DL once). She even had it out looking at it again yesterday.
ETA: they do have a "boy" version of that book too, it's Mickey
You don't need sharpies for the autograph books, just a large sized pen for the furry characters with big hands. You do need sharpies if you're autographing a pillowcase, picture mat, hat, bag, etc.