When we went to WDW the first time, I got blank books at the Disney Store, and the kids have used them for several trips. They plan to bring them on the cruise this time too. You have to search a little bit, but then they are different from the ones everyone else has, and you can keep adding to the memories.
In addition to just plain blank books, they also have semi-blank address books (just with the letters along the sides), and one of my kids has that. They open the page to the right letter (needless to say, the Ms are PRETTY FULL!), and then they can find their favorites quickly.
One other pointer on this. Make sure you have a pretty good sized pen for the characters to use. Think about signing Mickey's or Pluto's autograph with one of those little ball point pens! It gets swallowed right up in their paws!